1. 문제https://www.acmicpc.net/problem/2302 2. 풀이고정석을 제외한 구간 사이에 양쪽으로만 자리를 바꿀 수 있는 경우의 수를 구하는 문제이다.처음에는 이게 왜 DP 문제일까? 고민했었는데, 결국 자리 자리에 앉는 것과 옆자리에 앉는 2가지 선택은 바로 이전 사람이 어디 앉느냐에 따라 결정되므로 점화식을 세울 수 있었다. 좌석이 n개 있고, 내가 앉을 자리가 n번째에 위치한다고 가정해보면,1) n 자리에 앉는 경우: n-1번째까지 앉은 값2) n-1 자리에 앉는 경우: n-2번째까지 앉은 값 즉, 좌석 선택 여부 상태값에 따라 이전 n-1, n-2까지의 선택이 답이 된다. 여기서 n=1,2,3... 늘려가면서 숫자를 나열해보면 결국 작은 문제의 해답을 구하면 n까지의 문제도..

1. 문제https://www.acmicpc.net/problem/2156 2. 풀이포도주를 연속 2번 마실 수 있을 때 최대한 많은 양의 포도주를 시식하는 방법을 찾는 문제이다.예를 들어 6개의 잔이 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어있을 때 1번째, 2번째, 4번째, 5번째 잔을 선택하면 최대로 33을 마실 수 있다. 이 문제의 함정은 바로 연속해서 몇 잔 마셨는지를 어떻게 따지느냐이다.단순히 마실까, 말까 2가지 조건으로는 안 풀린다. DP에서 가장 중요한 것은 현재 선택이 '과거 선택'에 영향을 받는가이다.여기서는 3잔 연속 금지 때문에 현재 잔을 마시려면 이전 1~2개 잔 상태가 어떤지 반드시 체크해야 한다.우선 상태(State)는 연속으로 몇 잔 마셨는지이다. 그래서 상태..

1. 문제https://www.acmicpc.net/problem/9465 2. 풀이이 문제는 2*n 으로 구성된 스티커에 각각 점수가 부여되어 있을 때, 점수의 총합이 최대가 되도록 스티커를 떼는 경우를 찾는 문제이다.하나의 스티커를 뜯게 되면 인접한 스티커는 찢어져서 모두 사용할 수 없게 된다. 즉, 대각선으로 뜯거나 한 칸을 건너 뛰어서 뜯을 수 있다.좌측 1열에서부터 스티커를 뜯는다고 가정했을 때, 현재 어떤 스티커를 선택하느냐에 따라 다음 2열에서의 선택에 영향을 주게 된다.1열에 위치한(위에서부터) 50, 30 중에 50이 더 크니까 우선 선택한다고 해보자.그럼 50과 인접한 30, 10은 찢어지므로 다음에 선택할 수 없다.2열에서 남은 스티커는 50을 선택한다면 똑같이 인접한 10, 70은 ..

1. 문제https://www.acmicpc.net/problem/11057 2. 풀이이 문제 보자마자 10844번 쉬운 계단 수 문제가 생각났다.숫자의 마지막 자리에 의해 다음 수가 정해지는 패턴이 비슷한거같다.10844 쉬운 계단 수 풀이 자릿수 DP 문제를 풀 때는 N을 늘려가면서 규칙을 찾는 접근보다는, 어떤 상태(State)를 기준으로 규칙을 써야 하는지 감을 잡아야 한다.상태 전이가 어떻게 이루어지는지, 규칙을 만족하는 조합의 개수가 몇 개인지 세야 한다. (이 과정이 너무 어렵긴 하다..) 이 문제에서 상태(State)는 2가지이다.숫자의 길이마지막 숫자그 다음으로 상태가 어떤 조건에 따라 변화하는지 찾아보자.길이가 n이고 마지막 숫자가 i인 오르막 수를 찾을 때 바로 이전(n-1) 수의 마..

1. 문제https://www.acmicpc.net/problem/10844 2. 풀이인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다. 즉 다음 올 숫자는 이전의 숫자보다 1이 작거나 커야한다.그리고 0으로 시작하는 수는 계단 수가 아니다. 마지막 끝자리 숫자의 의해 다음 숫자가 결정되는 구조이다.예를 들어 1234 숫자에서 마지막 자리 숫자를 추가한다고 가정했을 때, 마지막 자리 숫자가 '4'이고, 그 앞 숫자는 3 또는 5이어야만 한다.1234512545이미 앞 숫자가 3이므로 다음 올 숫자는 5밖에 없다. 만약 마지막 숫자가 0이면 어떻게 될까?1010앞뒤 숫자는 무조건 1밖에 못 온다. 만약 마지막 숫자가 9라면789앞뒤 숫자는 무조건 8밖에 못 온다. 여기까지는 쉽게 접근했는데.. dp..

1. 문제https://www.acmicpc.net/problem/9095 2. 풀이이 문제는 DP로 풀 수 있다. 작은 문제가 반복되고 해당 최적 결과값을 통해 최종 답을 찾을 수 있으므로 DP의 두 가지 조건을 만족한다.1) Overlapping Subproblems (겹치는 부분 문제)2) Optimal Substructure (최적 부분 구조) 예시를 통해 알아보자. 우선 dp[1]은 1로만 나타낼 수 있으므로 1가지이다. 1) n = 11dp[1] = 1 2) n = 21 + 12dp[2] = 2 3) n = 31 + 1 + 12 + 11 + 23dp[3] = 4 4) n = 41 + 1 + 1 + 12 + 1 + 11 + 2 + 13 + 11 + 1 + 22 + 21 + 3dp[4] = 7 ..

1. 문제https://www.acmicpc.net/problem/1463 2. 풀이이 문제는 DP로 풀 수 있다. DP로 풀 수 있는지 어떻게 알 수 있을까?DP인지 아닌지 확인하려면 2가지 조건이 만족되어야 한다. 1) Overlapping Subproblems (겹치는 부분 문제)2) Optimal Substructure (최적 부분 구조) 예를 들어, 숫자 5를 1로 만들기 위해서는 아래와 같은 방법이 있을 것이다. 5 -> 4 -> 3 -> 2 -> 15 -> 4 -> 3 -> 15 -> 4 -> 2 -> 1 숫자 5를 1로 만들기 위해서는 거치는 과정이 여러 경우의 수가 있지만, 그 이전의 숫자들이 1이 되는 과정을 거쳐서 진행되는 것을 알 수 있다. 따라서 1) Overlapping Subp..