https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 그래프 탐색과 배낭 문제를 섞어놓은 문제였다. 1. 일단 주어진 그래프를 DFS로 탐색하여 배열에 [원소의 개수(우는 아이들의 수), 총 캔디 개수] 를 추가하였고 2. 이 배열을 가지고 dp를 활용하여 배낭 문제를 푸는 방식으로 풀었다. dp[i][j] = j 명의 아이들이 울면 어른들이 들킬 때 i번째 배열의..
알고리즘💻/DP
https://www.acmicpc.net/problem/11568 11568번: 민균이의 계략 민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 www.acmicpc.net 가장 긴 증가하는 부분 수열 문제인데, 문제가 처음 접하는 유형이라 어려웠다. 검색해보니 dp로 푸는 방법과 이진탐색을 이용하는 방법 두 가지가 있던데, 일단 dp로 풀어보았다. dp[i] = num[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이, 1로 초기화 dp[i] = 0~i-1까지 중 num[i]보다 작은 인덱스의 dp값 + 1과 dp[i]중 max값 갱신 import s..
https://www.acmicpc.net/problem/1451 1451번: 직사각형으로 나누기 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이 www.acmicpc.net 1. (0,0)을 왼쪽 위 꼭짓점으로 하고 (i,j)를 오른쪽 아래 꼭짓점으로 하는 직사각형의 누적합을 dp[i][j]에 저장 dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1] 2. (0,0)을 포함한 작은 사각형이 (0~N-2, 0~M-2) 인 경우 3. (0,0)을 포함한 작은 사각형이 dp[i][M-1]인 경우 4. ..
https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이것도 꽤 자주? 접했던 유형의 문제였다. n을 1, 2, 3의 합으로 나타내야 할 때 가능한 경우는 n-1 + 1 , n-2 + 2, n-3 + 3의 세 가지 경우이므로 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 로 구할 수 있다. 초기값 dp[1] = 1 //1 dp[2] = 2 // 2, 1+1 dp[3] = 4 //3, 2+1, 1+2, 1+1+1 import sys input = sys.stdin.readline T = int(input()) dp = [0] * 1..
https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 이것도 dp를 활용하여 푸는 기본적인 유형이었다. 간단하게 점화식을 짤 수 있었다. import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = [] for _ in range(N): arr.append(list(map(int, input().split()))) dp = [[0]*M for _ in rang..
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net dp를 통해 푸는 방법을 생각하는 것은 어렵지 않았다. n=0, n=1인 경우는 초기값으로 두고 dp[i][j] = arr[i][j] + max(dp[i-1][j-1], dp[i-1][j]) 로 점화식을 생각했는데, 이렇게 하면 j = 0일 때 인덱스에러가 나기 때문에 dp를 [n][n+1] 로 설정하였다. 그 다음에는 n = 0, n = 1일때 예외처리를 하지않아서 인덱스에러가 나왔다..ㅎㅎ import sys input = sys.stdin.readline n = ..
www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제풀이: dp를 어떻게 짜야 할 지 생각해내는 것이 어려웠다. 최솟값을 더하는 방법으로 하자니 동일한 비용이 나오는 경우를 고려하는 것이 어려웠고.. 그래서 각각의 경우를 모두 구하는 것이구나 하는 걸 깨달았다..(사실 힌트를 좀 받았다..) 그걸 깨닫고 나니 푸는 것은 간단했다. import sys N = int(sys.stdin.readline()) cost = [] for _ in ..
www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제풀이: dp[0] = [1,0] dp[1] = [0,1] dp[i][0] = dp[i-1][0] + dp[i-2][0] dp[i][1] = dp[i-1][1] + dp[i-2][1] 이미 구해놓은 수열은 반복하여 구하지 않고 바로 출력할 수 있도록 idx를 매번 업데이트 해주었다. import sys T = int(sys.stdin.readline()) dp = [[0,0] for _ in range(41)] dp[0] = [1,0] dp[1] = [0,1] idx = 2 for _ in range(T)..
www.acmicpc.net/problem/13301 13301번: 타일 장식물 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개 www.acmicpc.net 문제풀이: 기본적인 dp 활용 문제인 것 같다. dp[1] = 1, dp[2] = 1로 초기화하고 (편하게 하기 위해 인덱스를 1부터 시작했다.) dp[i] = dp[i-1] + dp[i-2]로 구했다. dp를 구하면서 동시에 둘레의 길이도 구했다. import sys N = int(sys.stdin.readline()) dp = [0]*81 length = [0]*81 dp[1] = 1 dp[2] = 1 len..
www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제풀이: DP를 이용해서.. 1부터 N까지 숫자의 최소 표현 개수를 모두 구한다. 구하는 방법을 생각해내는 게 어려웠는데, dp[0]=0, dp[1]=1 이라는 초기값을 넣어주고 2~N까지 i를 돌면서 i에서 i보다 같거나 작은 제곱 수를 하나씩 빼면서 최솟값을 갱신하는 방식으로 풀었다. 그래서 제곱 수의 배열인 arr도 따로 만들었고, 제곱한 값이 N보다 같거나 작은 경우..
