L.O.K

2156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net ◎ 문제풀이 일렬로 나열된 와인을 마실 때, 최대 비용으로 마시는 경우를 구하는 문제이다. 단, 연속으로 3잔을 마시지 못한다.  와인의 모든 경우를 따져서 최대 비용을 구하는 문제이니 메모리제이션을 활용한 DP로 풀어주는 것이 좋다. DP로 풀려면 점화식을 구해야 한다.     와인 3잔이 있다. 와인은 마시거나 안 마시거나 2가지 경우를 선택할 수 있다. 그럼 총 8가지 경우의 수가 나온다. 1) O O O2) O O X3) O X O4) X O O5) X X O..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net ◎ 문제풀이 처음에 문제를 잘못 접근하여 푸는데 시간이 걸렸다. 이웃한 집과 같은 색상이면 안 되고 비용을 최소로 하는 문제이다. 그래서 정말 단순하게 생각했다. dp[n]이 n번째 집까지 색칠하는데 걸리는 최소비용이라면, 이는 dp[n-1]에서 이웃하지 않는 색상 중 최솟값을 더하면 구할 수 있다고 생각했다. ( 그리디 관점으로 생각했다. ) 그러나 이런 생각은 모든 경우를 고려하지 않은 풀이이다. 이번 문제는 최적해를 구하는 문제가 아니..

https://www.acmicpc.net/problem/2225 2225번: 합분해첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net  ◎ 문제풀이 합해야 하는 K가 정해져 있어 어려운 문제였다.    5가 되는 경우는 6가지가 있다. 0에 +5를 하는 경우1에 +4를 하는 경우2에 +3을 하는 경우3에 +2를 하는 경우4에 +1을 하는 경우5에 +0을 하는 경우 k는 3이므로,+0,+1,+2,+3,+4,+5은 2개의 합으로 구성되어야 한다. 이를 점화식으로 표현하면 아래와 같다. dp[5][3] = dp[0][2] + dp[1][2] + dp[2][2] + dp[3][2] + dp[4][2] + dp[5][2] dp[n][k] = dp[0][k-1] + d..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net ◎ 문제풀이 n까지의 정수 중 최대의 연속된 합을 구하는 문제이다. n까지의 정수 중에 연속된 최대의 합은 두 가지 경우가 있다. 1) 연속된 합이 n까지 연속되는 경우 2) 연속된 합이 n까지 연속되지 않은 경우 2가지 경우 중 최대값을 구하면 된다. ◎ 코드 #BOJ1912 연속합 (dp) import sys input = sys.stdin.readline n = int(input()) arr = lis..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ◎문제풀이 DP문제를 풀 때, 이차원 리스트를 발상이 어려워 문제풀이가 쉽지 않았다. 각 자리에는 0-9의 수가 들어갈 수 있다. ( 첫번째 자리에는 0이 들어갈 수 없다. ) 8은 두 가지 경우로 생성된다. 1) 7에서 +1 한 경우 2) 9에서 -1 한 경우 두 경우는 독립사건으로 경우의수는 합으로 구한다. d[8] = d[7] +d[9] 1-8까지는 이와 동일하지만 0과 9는 다르다. 0과 9는 한 가지 경우에서 나온다. d[9] = d[8] d[0] = d[1] 여기서 이전 자리와 현재 자리를 구분해야 ..

https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net ◎문제풀이 기저조건( +1, +2, +3)이 주어지고 목표(정수 n)의 구하는 경우의 수를 구하는 문제이므로 DP이다. n이 10이라고 가정하고 +1,+2,+3으로 10을 만드는 방법의 수를 d[10]이라고 해보자. 이때 사건은 총 3가지이다. 첫번째 사건 : +1로 끝나는 경우 = d[9] 두번째 사건 : +2로 끝나는 경우 = d[8] 세번째 사건 : +3으로 끝나는 경우 = d[7] 세 가지 사건은 독립사건이다. 그러므로 점화식은 아래와 같다..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)www.acmicpc.net ◎ 문제풀이 카드팩 안에는 1 ~ N개의 카드가 들어있다. 카드팩의 비용은 개수에 상관없이 제각각이다. 민규가 N개의 카드를 구할 수 있는 비용의 최댓값을 구하는 문제이다. N개 목표가 주어졌고 1~N개가 카드팩으로 묶여 있으므로 기저조건이다. 기저조건으로 목표를 구하는 문제이므로 DP로 풀면된다. 4개의 카드의 최댓값을 구해보자. 4개의 카드를 구할 수 있는 사건은 4개가 있다. 첫번째 사건 : 1개 팩 ..

9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ◎ 문제풀이 1,2,3 기저조건이 있고 목표값까지 가는 경우의 수를 구하는 문제이니 DP문제이다. 1,2,3으로 10을 구하는 경우의 수를 d(10)이라고 하자. 10을 구하는 사건은 3가지 사건이 있다. 사건 ① : 9 + 1 사건 ② : 8 + 2 사건 ③ : 7 + 3 3가지 사건은 모두 독립사건이다. 그러므로 d(10) = d(9) + d(8) + d(7)이 성립된다. dp는 기저조건으로 독립사건을 구하여 점화식을 도출하는 것이 중요하다. ◎ 코드 n = int(input()) def dp(value) : d = [0]*11 d[1],d[2],d[3] ..

◎문제 N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. - 입력 조건 첫째 줄에 N,M이 주어진다(1

◎ 문제 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어, 2X3 크기의 바닥을 채우는 경우의 수는 5가지이다. - 입력 조건 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000) - 출력 조건 첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다. - 입력 예시 3 - 출력 예시 5 ◎ 문제풀이 작은 타일로 큰 영역을 채우는 문제이다. 부분으로 목표를 만드는 문제이므로 DP를 연상할 수 있다. 영역은 NX2로 세로는 고정되어 있고 가로길이가 동적으..