HOIT_B

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net N = 1인 경우 1가지씩 => 9 N =2인 경우 12인 경우 0번자리는 1 0번 자리 1번 자리 1 2,0 2 1,3 3 2,4 4 3,5 5 4,6 6 6,7 7 6,8 8 7,9 9 8 N =3인 경우 0번자리 1번 2번 1 2,0 2(1,3),0(1) 2 1,3 1(0,2),3(2,4) 3 2,4 위와 같은 원리로 아래 쭉 4 3,5 - 5 4,6 - 6 5,7 - 7 6,8 - 8 7,9 - 9 8 - ARR[a][b] : a번째가 b일 때 나올 수 있는 수 Arr[2][1] = Arr[1][0..

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 먼저 규칙을 찾았다. 규칙 n 방법 방법의 수 1 1 1 2 1+1 , 2 2 3 1+1+1, 1+2, 2+1, 3 4 4 1+1+1+1, 1+1+2, 1+2+1,2+1+1, 2+2, 1+3, 3+1 7 5 1+1+1+1+1, 1+1+1+2,1+1+2+1,1+2+1+1+,2+1+1+1,2+2+1,2+1+2,1+2+2, 2+3+3+2, 3+1+1,1+3+1,1+1+3 13 6 1+1+1+3, 1+1+3+1, 1+3+1+1, 3+1+1+1, 1+1+2+2, 1+2+2+1, 1+2+1+2, 2+..

문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 코드 다 만들었는데 제출 누르고 날아가서 의욕을 잃었다. 따라서 이번엔 코드가 없다. 며칠이 지나야 토마토가 다 익는지 구하는 문제 익은 토마토와 인접한 토마토는 하루가 지나면 익는다. (인접 : 상하좌우) 2

문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 연결된 노드의 개수를 찾는 문제라서 BFS로 풀었다. #include #include #include using namespace std; int visit[101]={0,}; //방문여부 int cnt =0; int n,m=0; void bfs(int num , vector v) { queue q; visit[num] = 1; q.push(num); while(!q.empty()) { int c..

문제 https://www.acmicpc.net/workbook/view/3492 문제집: 파라메트릭 서치(이분탐색(binary)/삼분탐색(ternary)) (daejjyu) www.acmicpc.net 변수명을 start mid end 로 하는게 편할것같다. 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) => 때문에 sum은 long long 4 7 20 15 10 17 start end mid sum sum m answer 0 20 10 10+5+2 =17 sum >= m 10 1511 20 15 5+2=7 sum == 7 15 16 20 18 2 sum < m 15 16 17 16 ..

문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 파라메트릭 서치 최적화 문제( 최소/최대값 구하는 문제 ) -> 결정 문제 바꾸어푸는 것. 그냥 탐색으로 풀면 시간초과를 받는다. 탐색인데 수가 크다면 의심해보자. #include #include #include #include #include #include #include #include using namespace std; int main() { ios_ba..

문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 처음 생각은 2개의 시작점에서 모든 대각선을 합했을 때 더 큰 값을 출력하는 것 이었다. 50 10 100 20 40 90 50 70 10 60 대각선만 합한 경우 (0,0)부터 대각선의 합 : 50+50+100+10+40 = 250 (1,0)부터 대각선의 합 : 90+10+70+20+60 = 250 (0,0) (0,1) (0,2) (0,3) (0,4) (1,0) (1,1) (1,..

문제 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 처음 아이디어 시작점, 끝 점 이용 처음 입력한 두 점을 시작점, 끝 점에 넣는다. linear 시작점에 첫 시작점을 넣어준다. 다음 시작점이 시작점과 끝 점 사이라면 계속 진행 아니라면 끝점 - 처음 시작점을 cnt에 넣어주고 linear 시작점에 다음 시작점을 넣는다. 예제로 보면 ( 1 , 3 ) 시작점 : 1 , 끝 점 : 3 linear시작점 : 1 ..