코딩테스트
2022. 1. 5.
[C++] (백준 1463번) 1로 만들기
문제출처: 백준 (baekjoon) 문제 링크: https://www.acmicpc.net/problem/1463 난이도: ★★☆☆☆ 문제 분류: 다이나믹 프로그래밍(dp) [문제] [분석] 다이나믹 프로그래밍의 기본은 탑다운이 아닌, 바텀업(bottom up)이다. 따라서 문제에 해당하는 재귀식을 세운 뒤에 문제를 풀었다. 배열의 이름을 col 이라고 지었고 idx=0부터 차례대로 채웠다. n=1 일 경우는 원래 1이기 때문에 연산을 하지 않으므로 연산 횟수가 0이고 n=2 or n=3 일 경우는 조건 1과 조건 2에 의해 연산 횟수가 1이 된다. 여기까지가 base case이다. 다음은 recursive case이다. n이 3보다 클 경우, for문을 돌며 배열을 채워간다. n=4일 경우, 조건 2와..