고양이 두 잔

목차 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 지난 문제에서 두 가지 값의 조합으로 최솟값을 만들었던 것에 비해, 이번 문제에서는 세 가지 연산을 이용해 최솟값을 찾는다. 먼저 0으로 초기화한 (N + 1) 크기의 dp리스트를 만들고 2부터 시작해 N까지 반복문을 돌며 리스트를 채워나간다. 여기서 2부터 시작..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 조금씩 난이도가 오르는 동적계획법 문제다. 하지만 기본적인 접근 방식은 다를 것이 없어서, 어느 연산을 어떤 식으로 배치하는 지만 정해주면 되는 문제. 우선 주어진 수보다 1이 더 큰 길이를 가진 memo 배열을 선언한다. 그리고 memo[1]에는 초기값으로 0을 입력..