[백준 1463번] 1로 만들기 (Python 파이썬) 풀이 방법

🎧나의 사춘기에게 - 볼빨간사춘기

눈물버튼 노래다 ㅠㅠ 동시에 열심히 살아야겠다는 마음가짐을 다잡도록 해주는 노래 ,,

 

 

 

백준 1463번 <1로 만들기> 문제 보기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

백준 1463번 <1로 만들기> 문제 풀이

def solution():
  N = int(input())
  answer = [0]*(N+1)

  for i in range(2, N+1):
    answer[i] = answer[i-1]+1

    if i%2 == 0:
      answer[i] = min(answer[i], answer[i//2]+1)

    if i%3 == 0:
      answer[i] = min(answer[i], answer[i//3]+1)
  
  print(answer[N])

solution()

DP 중 bottom-up 방식을 사용해 풀었다. 정수 X에 사용할 수 있는 연산은 총 세 가지가 주어진다.

answer[i] = answer[i-1]+1 는 그 중 3번(1을 뺀다)의 경우를 계산한 초기값이다. 만약, 해당 수가 2의 배수라면 3번 방식인 초기값과 2번 방식인 answer[i//2]+1 값을 비교해주게 된다. 이때 answer[i//2]+1은 answer[i]일 때 i를 2로 나눴을 때의 최소값 + 수행할 때 걸리는 1번을 의미한다. 마찬가지로, 해당 수가 3의 배수라면 초기값과 3으로 나눴을 때의 최소값 + 1의 비교를 통해 최소값을 저장해준다.

 

 

 

첫 번째 도전

def solution():
    answer = 0
    
    N = int(input())
    
    if N == 1:
        print('0')
        return 0

    if N == 2 or N == 3:
        print('1')
        return 1
    
    if N & (N-1) == 0:
        answer = len(bin(N))-3
        print(answer)
        return answer
        
    while N > 3:
        if N % 3 == 2:
            if N  % 2 == 1:
                N -= 2
                answer += 1
            N /= 2
            answer += 1
        elif N % 3 == 1:
            N -= 1
            answer += 1
            N /= 3
            answer += 1
        else:
            N /= 3
            answer += 1

    print(answer+1)
    return answer+1

solution()

규칙을 찾아 단순 구현을 하면 풀리는 문제인 줄 알았다. 결과는 틀렸습니다 :) 생각한 사고는 아래와 같다.

 

다른 풀이로는 DP top down 방식으로 재귀로 풀어내는 방법이 있다. 또 BFS를 사용해도 풀 수 있는 문제라고 한다. 다음에 에 풀이가 생각이 안날때쯤 다시 풀어보려 한다.

 

 

 

종일 마음이 너무 무거운 하루였다. 벅차다.