컴굥일지

문제 https://www.acmicpc.net/problem/1463 문제 내용 할 수 있는 연산은 3가지이다. 3으로 나누거나, 2로 나누거나, 1을 빼는 것 위 3가지 연산을 최소한으로 사용해서 입력받은 수를 1로 만들면 된다. 문제 풀이 문제를 보면 dynamic programming이라는 것은 짐작이 올 것이다. dp이긴 한데 조건을 어떻게 새워야 할까? 2나 3으로 나누어 떨어지면 그냥 나누는 것을 선택하는게 좋을까? => 아니다 문제에서 준 힌트를 보니 10의 경우 10 -> 9 -> 3 -> 1의 순서가 가장 연산이 적다고 되어있었다. 10의 경우 2로 나누어 떨어지지만, 1을 먼저 뺀 경우가 더 연산 숫자가 적다. 이를 적용해보자면, 1) 2 또는 3으로 나누어지지 않는다 => 1을 뺀다..