[알고리즘] 1로 만들기 - DP

문제 링크

1로 만들기 : https://www.acmicpc.net/problem/1463

 

문제탐색

기본 원리 탐색

• 정수 N이 주어졌을때 [3으로 나누기], [2로 나누기], [1을 빼기] 세가지중 하나를 수행하는것을 반복하여 최소한의 연산으로 1을 만들어야 하는 문제입니다. 
  
  • 얼핏보면 우선순위를 두어 그리디를 적용할수 있을것 처럼 보이지만 불가 합니다. (ex 10)

 

시간복잡도와 알고리즘

• 시간제한 : 0.15초
  • 약 1500만 번의 연산, 매우 까다로운 시간제한을 가지고 있습니다.
• N 최대값 : 10^6 = 1,000,000

 

해당 문제는 규칙을 찾기 힘들고 실제로 동작을 시켜서 경우의 수를 찾아야합니다.

하지만 완전탐색을 적용하기엔 N의수가 매우크며, 시간제한이 까다롭습니다.

 

그러므로 동적 계획법 알고리즘을 통해 접근합니다.

 

먼저 동적 계획법의 기본적인 아이디어인  "하나의 큰 문제를 여러 작은문제로 나누기" 부터 수행합니다.

 

에를들어 숫자 10을 기준으로 탐색해 봅니다.

 

정수 10이 1까지 최소한의 수행으로 갈 수 있는 시작 방법은 3가지를 생각해볼 수 있습니다.

1.  3으로 나눈후 진행 =>불가능
2.  2로 나눈 후 진행 =>5
3.  1을 뺀 후 진행 =>9

  이때 가능한 2, 3번의 경우 수행하게되면 동일하게 1회가 소모되며 다음 작은 문제로 넘어갑니다.

이 때 만약 9나 5가 1이될수있는 최소 시행횟수를 알고있다면 다음과같이 10의 연산 최솟값을 구할 수 있습니다.

 

10의 연산 최솟값 =   5의 연산최소값 과 9의 연산최소값중 작은값  + 1 

 

그리고 5의 연산 최소값과 9의 연산최소값은 같은원리로 작은 문제로 만들 수 있고, 그 끝은 3 혹은 2 가 되며 그 답을 구할 수 있습니다.

 

해당 원리로 차근차근 각 경로의 숫자들의 연산 최소값을 구해나가며 정답지를 저장합니다.

만약 정답지에 해당 값이 있다면 경로의 숫자중 중복되는 수는 해당 정답지를 참조하여 구합니다 (시간 절약)

 

=>위의 규칙에 따라 동적 계획법을 수행합니다.

 

코드설계하기

1. N값을 입력받습니다.
2. 정답지 딕셔너리를 생성하고 1:0,2:1.3:1을 미리 생성합니다. 
3. 4~N까지 for문을 순회하며 다음 4-7규칙을 수행합니다. 
4. 최소값을 구할 리스트를 선언합니다.
5. 3으로 나누어떨어진다면 3으로 나눈값을 정답지에서 찾아 리스트에 담습니다.
   • (정답지에 값은 무조건 존재합니다. 이유는 가장 작은 수 부터 정답지에 입력해 나가고 있기 때문입니다.)
6. 5의 과정을 2로나누기와 1빼기도 반복합니다.
7. 5,6 과정에서 만들어진 리스트의 최소값+1을 정답지에 기록합니다.
8. 정답지 딕셔너리에서 N값을 출력합니다.

 

시도회차 수정사항

• 1회차 : 해당 접근방식 자체가 재귀함수를 사용하다보니  RecursionError: maximum recursion depth exceeded in comparison 함수 최대 수가 초과되는 현상이 발생.
  • => For문을 통한 DP를 구현해야 합니다.  (실패코드는 맨아래에 더보기)
• 2회차 : 정답지 생성시 1에대한 정답(0)을 미리 만들어놓지 않아 런타임 에러 (KeyError) 발생
  • 정답지 생성시 1:0도 포함

정답코드

import sys

def choceAndEnding(N):
    answer = {1: 0, 2:1, 3:1}  # 1은 연산 필요 없음

    for i in range(4, N + 1): # 작은수부터 차근차근 계산해 나가기
        alive = []

        # 3으로 나누어 떨어지는 경우
        if i % 3 == 0:
            alive.append(answer[i // 3])

        # 2로 나누어 떨어지는 경우
        if i % 2 == 0:
            alive.append(answer[i // 2])

        # 1을 빼는 경우
        alive.append(answer[i - 1])

        answer[i] = min(alive) + 1 #정답지에 최소값 저장

    return answer[N] #정수 N의 정답 반환

N = int(sys.stdin.readline())

# 결과 출력
print(choceAndEnding(N))

 

 

실패 코드

코드설계하기

1. N값을 입력받습니다.
2. 딕셔너리(정답지)를 생성합니다. 안에는 3과 2의 정답을 입력해 둡니다.(1)
3. 아래 4-6 규칙을 수행하는 재귀함수를 선언합니다.
4. 입력받은 수를 3으로나누기, 2로 나누기, 1을 빼기 를 수행한 수를 구합니다.(나누어 떨어지는 경우만)
5. 구한 수들이 정답지에 있는지 확인한 후 없다면 재귀함수(자기자신)를 통해 구합니다.
6. 3개의 수들의 연산 최소값중 가장 작은 값 +1 을 반환합니다.
7. 재귀함수에 입력받은 N값을 넣고 결과를 출력합니다.

코드

import sys
def choceAndEnding(N):#N으로 들어오는 수는 무조건 4 이상입니다.
    # print(N) 
    alive=[]
    if N%3==0:  #3으로 나눈 수
        a=N//3    
        if a in answer:      #정답지에 있으면 바로 불러오기
            a=answer[a]
        else:
            a=choceAndEnding(a) # 없으면 재귀함수 실행
        alive.append(a)
    if N%2==0:#2으로 나눈 수
        b=N//2
        if b in answer:
            b=answer[b]
        else:
            b=choceAndEnding(b)
        alive.append(b)
    c=N-1 #1을 뺀 수
    if c in answer:
        c=answer[c]
    else:
        c=choceAndEnding(c)
    alive.append(c)
    
    answer[N]=min(alive)+1
    return min(alive)+1
     
    

    return 0

N=int(sys.stdin.readline())

answer={2:1,3:1}

print(choceAndEnding(N))  #재귀함수 실행