BOJ
[ 백준 1463 ] - 1로 만들기 (Kotlin)
1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 이해 & 기본 개념 아래 3가지 방법을 통해 입력 받은 수를 1로 만드는 것 X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 최소 횟수를 구해야하는 문제 3으로 나누는게 1을 빼는 것보다 수가 훨씬 작아지므로 자칫하면 그리디 문제로 오해할 수 있다. ex) n = 10 10 -> 9 -> 3 -> 1 10 -> 5 -> 4 -> 2 -> 1 이처럼 가능한 큰 수로 나누는 것보다 1을 먼저 빼는 경우가 최소 횟수가 될 수도 있기 때문에 dp를 이용한다. 최종 풀이 파란색이 처음 계산 되는 부분 빨간색이 중복 계산 되는 ..
