Jubil의 프로그래밍 블로그

9251_LCS 링크 https://www.acmicpc.net/problem/9251 풀이 처음에 편의를 위해서 0행과 0열을 0으로 세팅해줍니다. DP[i][j]를 LCS(i까지의 string2, j까지의 string1)라고 정의합시다. LCS로 비교하는 string의 마지막 문자가 같다면, LCS(i까지의 string2, j까지의 string1) = LCS(i-1까지의 string2, j-1까지의 string1) + 1이 됩니다. 즉, if(string2[i] == string1[j]) DP[i][j] = DP[i-1][j-1] + 1이 됩니다. LCS로 비교하는 string의 마지막 문자가 다르다면, LCS(i까지의 string2, j까지의 string1) = max(LCS(i-1까지의 strin..

2156_포도주 시식 링크 https://www.acmicpc.net/problem/2156 풀이1 A[i]를 i번째 포도주의 양, DP[N][L]을 N번째 마신 포도주의 양, 연속 L번째라고 정의하겠습니다. 우선 i번째에 0번 연속으로 먹는다(이번에 먹지 않는다)고 했을 때, DP[i][0]을 정의할 수 있습니다. 이번에 먹지 않으니 변화가 없다는 뜻입니다. 그리고 전에 먹었는지 먹지 않았는지는 상관하지 않기 때문에 전 단계에서 먹은 양 중에 최대로 먹은 양을 가져오면 됩니다. DP[i][0] = max(DP[i-1][0], DP[i-1][1], DP[i-1][2]) 1번 연속으로 먹는다(이번에 먹고 전 단계에서 먹지 않았다)고 했을 때, DP[i][1]을 정의할 수 있습니다. 이번에 먹으니 A[i]를..

1463_1로 만들기 링크 https://www.acmicpc.net/problem/1463 풀이 우선 DP[N]을 정수 N을 1로 만드는 데 필요한 최소 연산 횟수라고 정의합시다. N은 N-1에서 1을 더해 만들 수 있고, N/2에서 2를 곱해 만들 수 있고, N/3에서 3을 곱해 만들 수 있습니다. DP[N]은 DP[N-1]과 DP[N/2]와 DP[N/3]에서 한 번의 연산을 더 수행해서 만들 수 있습니다. 하지만 DP[N]은 최소 연산 횟수이기 때문에, DP[N] = min(DP[N-1]+1, DP[N/2]+1, DP[N/3]+1) 라는 식이 생깁니다. 이걸 조건마다 코드로 구현하면 됩니다. 코드

11052_붕어빵 판매하기 링크 https://www.acmicpc.net/problem/11052 풀이 붕어빵을 N개 팔아서 얻을 수 있는 최대 이익을 DP[N]이라고 정의하고, 붕어빵 N개 팔 때의 가격을 P[N]이라고 정의하겠습니다. 그리고 DP는 모두 0으로 초기화 하겠습니다. 위의 1 5 6 7 의 예제로 설명하겠습니다. 붕어빵 1개를 팔아야 한다면 D[1-1] + P[1] 하나뿐입니다. 참고로 DP[1-1] + P[1]은 1-1개 팔 때 최대 이익 + 1개 팔 때의 가격입니다. 붕어빵 2개를 팔아야 한다면 DP[2-1] + P[1] DP[2-2] + P[2] 중에 큰 값이 DP[2]가 될 것입니다. DP[2-1] + P[1]은 1+1=2고, DP[2-2] + P[2]는 0+5=5입니다. DP[..

오르막 수는 계단 수와 유사합니다.그 다음 수를 가기 위한 조건이 있기 때문에 마지막 자리를 저장해줘야 합니다. DP[N][10] 이렇게 선언해주면 0~9의 마지막 숫자를 저장해 줄 수 있습니다.그리고 0으로 시작할 수 있기 때문에 DP[1][0~9]를 모두 1로 초기화 합니다. 마지막 자리가 0이라면 0~9까지의 숫자가 뒤에 올 수 있습니다.DP[N][0~9] += DP[N-1][0] 마지막 자리가 1이라면 1~9까지의 숫자가 뒤에 올 수 있습니다.DP[N][1~9] += DP[N-1][1] ... 마지막 자리가 9라면 9만 뒤에 올 수 있습니다.DP[N][9] += DP[N-1][9] 그럼 i는 2부터 n까지, j는 0부터 9까지, k는 j부터 9까지 3중 for문을 돌리면 됩니다.DP[i][k] +..

1912_연속합 링크 https://www.acmicpc.net/problem/1912 풀이 간단하게 풀 수 있는 문제입니다. 우선 가장 큰 값을 구해야 하기 때문에 max를 선언합니다. 연속합의 최댓값의 최솟값(-1000)-1로 초기화 합니다. DP 배열에 값을 입력 받고, i=1부터 n까지 for문을 돌립니다. 그리고 DP[i] = MAX(DP[i], DP[i-1] + DP[i])를 해줍니다. 굳이 전의 연속합과 더한 것보다 이번 숫자가 크면 더할 필요가 없기 때문입니다. 연속해서 더한 게 크다면 더해야죠. 대신에 그 다음 라인에 max = MAX(max, DP[n])로 max 값을 구해주는 일도 잊지 말아야 합니다. 코드

2193_이친수 링크 https://www.acmicpc.net/problem/2193 풀이 조건을 보면 0으로 시작하지 않고, 1이 연속으로 올 수 없습니다. 그럼 마지막 자리(0, 1)를 담을 수 있는 DP[N][2]를 만든다고 가정합시다. N이 1이면 0이 올 수 없으므로 DP[1][0] = 0, DP[1][1] = 1이 됩니다. 그리고 0으로 올 수 있는 건 마지막 자리가 0과 1 다 가능하고, 1로 올 수 있는 건 마지막 자리가 0인 경우 밖에 없습니다. 이 조건을 이용해서 점화식을 정의해 보겠습니다. DP[N][0] = DP[N-1][0] + DP[N-1][1] DP[N][1] = DP[N-1][0] 입니다. 이렇게 코드를 짜고 마지막에 DP[N][0] + DP[N][1]을 출력하면 됩니다. ..

9461_파도반 수열 링크 https://www.acmicpc.net/problem/9461 풀이 그림으로 설명하겠습니다. P1 = 1, P2 = 1, P3 = 1, P4 = 2, P5 = 2, P6 = 3, P7 = 4, P8 = 5, P9 = 7, P10 = 9 빨간색 3은 P6이고 구성은 P5 + P1입니다. 빨간색 4는 P7이고 구성은 P6 + P2입니다. 빨간색 12는 P10이고 구성은 P9 + P5입니다. 그렇다면 파도반 수열의 점화식을 구할 수 있습니다. Pn = Pn-1 + Pn-5 (n >= 6) DP를 이용해서 코드를 짜봅시다. n은 100까지니 숫자가 커질 수 있습니다. long long으로 P[101]를 선언해야 합니다. 코드

2294_동전 2 링크 https://www.acmicpc.net/problem/2294 풀이 위 문제의 예제로 어떻게 풀어낼 수 있을 지 생각해 봅시다. 일단 0을 제외한 모든 배열의 인덱스를 10001로 초기화 해야합니다. 왜냐하면 최솟값을 구하는 문제이기 때문이죠. 그래서 나올 수 있는 최댓값보다 더 큰 값으로 초기화 했습니다(불가능한 경우까지 고려). 이제부터 1원을 이용해서 값을 만들어 봅시다. 1원을 만들려면, DP[1]과 DP[1-1]에 1원을 더하는 경우를 비교해야 합니다. DP[1]은 초기값 10001이고, DP[1-1]에 1원을 더하는 경우는 DP[0] + 1이기 때문에 1입니다. 1이 더 작기 때문에 DP[1] = DP[0] + 1로 채택합니다. 2원을 만들겠습니다. 원래 DP[2]는..

2293_동전 1 링크 https://www.acmicpc.net/problem/2293 풀이 일단 k원을 만들 수 있는 경우의 수를 담을 배열 DP[10001]과 가치를 가진 동전을 담을 배열 coin[101]을 만들어 줍니다. 그리고 DP[0]은 동전을 가지고 0원을 만들 경우의 수이니 1로 초기화 해줍니다. 예제로 설명을 하자면, 1원, 2원, 5원짜리 동전으로 10원을 만드는 경우의 수를 구해야 합니다. DP[n] = DP[n-1] + DP[n-2] + DP[n-5] 1원을 만들려면 0원에 + 1원을 해줍니다. 1가지 2원을 만들려면 0원에 + 2원을 해주거나 1원에 + 1원을 해줍니다. 2가지 3원을 만들려면 1원에 + 2원을 해주거나 2원에 + 1원을 해줍니다. 3가지 (2가지인데 중복이 생김..