백준 2342번 Dance Dance Revolution - 스위프트(Swift) 풀이
1. dp(index, left, right) : 현재 두 발의 위치가 left, right일 때 arr[index...]를 모두 밟는 최소 비용 2. dp(index, left, right) = min(왼쪽 발을 움직일 때 비용, 오른쪽 발을 움직일 때 비용) 1. dp(index, left, right) : 현재 두 발의 위치가 left, right일 때 arr[index...]를 모두 밟는 최소 비용 현재의 움직임이 나중에 어떤 영향을 미칠지 예상할 수 없으므로 다이나믹 프로그래밍으로 해결할 수 있다. 현재 두 발의 위치가 left, right일 때 arr[index...]를 모두 밟는 최소 비용을 dp(index, left, right)라고 정의하자. 위치가 5가지이므로 총 5*5*100,000개..
2022. 2. 3.
백준 17070번 파이프 옮기기 1 - 스위프트(Swift) 풀이
1. dp(row, col, direction) = 왼쪽 끝이 (row,col)에 위치하고 direction 방향으로 놓인 파이프를 (N,N)으로 옮기는 방법의 수 2. dp(row, col, direction) = ∑ dp(파이프가 이동할 수 있는 위치, 방향) 1. dp(row, col, direction) = 왼쪽 끝이 (row,col)에 위치하고 direction 방향으로 놓인 파이프를 (N,N)으로 옮기는 방법의 수 DP라는 방법만 떠올리고 나면 특별히 고려해줄 점 없이 그냥 구현하면 된다. dp(row, col, direction)을 위와 같이 정의한다. 2. dp(row, col, direction) = ∑ dp(파이프가 이동할 수 있는 위치, 방향) 파이프를 이동시킬 수 있는 모든 방법을 ..
2022. 1. 26.
백준 9465번 스티커 - 스위프트(Swift) 풀이
1. dp(n, up, down) = n번째 열의 위아래 스티커 존재 여부가 up, down일 때, n번째 열부터 끝까지 고려했을 때 얻을 수 있는 최대 점수 2. n번째 열의 위아래 스티커 모두 떼지 않는 경우의 최대 점수 = dp(n+1, 1, 1) 3. n번째 열의 위 스티커만 떼는 경우의 최대 점수 = stickers[0][n] + dp(n+1, 0, 1) 4. n번째 열의 아래 스티커만 떼는 경우의 최대 점수 = stickers[1][n] + dp(n+1, 1, 0) 5. dp(n, up, down) = max(2번 경우, 3번 경우, 4번 경우) 1. dp(n, up, down) = n번째 열의 위아래 스티커 존재 여부가 up, down일 때, n번째 열부터 끝까지 고려했을 때 얻을 수 있는 ..
2022. 1. 22.
