13392번: 방법을 출력하지 않는 숫자 맞추기, 2492번: 숫자 맞추기 - DP
1. 나사를 왼쪽으로 돌리면 아래의 모든 나사가 동일하게 왼쪽으로 돌아가며, 오른쪽으로 돌리면 그 나사만 오른쪽으로 돌아간다. 따라서 DP식을 아래와 같이 설정한다. \(dp[i][j]\) : \(i\)번째 나사가 왼쪽으로 \(j\)번 만큼 돌아갔을 때, 원하는 상태로 나사를 돌리는 횟수의 최솟값 이 상태에서 \(i\)번째 나사를 원하는 상태로 만들기 위해 오른쪽으로 돌린 횟수를 \(m\)이라 한다면, 나사를 원하는 상태로 만들기 위해 오른쪽으로 돌렸을 때의 최솟값은 다음과 같다.\(dp[i+1][j] + m\) 왼쪽으로 돌린 횟수는 그 반대인 \(10 - m\)이 된다. 나사를 원하는 상태로 만들기 위해 왼쪽으로 돌렸을 때의 최솟값은 다음과 같다.\(dp[i+1][j+10-m] + (10 - m)\)..
알고리즘/baekjoon
2024. 6. 18. 12:28
