알고리즘 다이나믹 프로그래밍 풀이 계단 별 점수를 저장하는 벡터 s와 계단 점수의 최대값을 저장하는 벡터 dy를 사용하였다. s[i] = i층 계단의 점수, dy[i] = i층 계단까지의 최대값 dy[1]=s[1] dy[2]=s[1]+s[2] dy[3]=s[3]+(s[1]과 s[2] 중 큰 값) dy[i]=s[i]+(dy[i-2]와 dy[i-3]+s[i-1] 중 큰 값) (n>3) s[i]+dy[i-2] (i 계단의 점수) + (i - 2 계단까지 가는 최대값) s[i]+dy[i-3]+s[i-1] (i 계단의 점수) + (i - 3계단까지 가는 최대값) + (i - 1 계단의 점수) 성공 코드 #include using namespace std; int main() { // freopen("input.t..
알고리즘 다이나믹 프로그래밍 풀이 h 2차원 벡터를 두어 똑같은 색이 이웃하지 않도록 h[i-1]의 값 중 최소 값을 이용하여 값을 누적해간다. 즉, h[i][1]은 i번째 집을 빨간색으로 칠할 때의 최소 비용, h[i][2]은 i번째 집을 초록색으로 칠할 때의 최소 비용, h[i][1]은 i번째 집을 파란색으로 칠할 때의 최소 비용이 된다. 그러면 h[n][1], h[n][2], h[n][3] 중 최소값이 답이 된다. 성공 코드 #include using namespace std; int main() { // freopen("input.txt", "rt", stdin); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, r,..
알고리즘 다이나믹 프로그래밍 풀이 타일은 | 또는 ㅡ 같은 모양을 가진다. 직사각형 2*n에서 n이 하나 증가하면 열이 한칸 더 생기는 것으로 | 만큼이 더 생기게 된다. 그러므로 2*n-1을 채우는 방법에 | 을 붙여주면 된다. 이 외의 경우의 수가 하나 더있는데 = 가로 두개가 마지막에 붙는 경우이다. 이 경우에는 2*n-2을 채우는 방법에 = 을 붙여주면 된다. 즉 직사각형 2*n을 채우는 방법의 수는 2*n-1을 채우는 방법의 수 + 2*n-2을 채우는 방법의 수가 된다. 벡터 dy를 이용하여 나타낼 수 있다. dy[1]은 | 로 채울 수 있는 방법이 하나이므로 1으로 초기화 dy[2]는 || 또는 = 로 채울 수 있는 방법이 두가지이므로 2로 초기화 한다. dy[1]=1 dy[2]=2 dy[n]..