BOJ(백준) 1463[1로 만들기]

백준 1463번 문제인 “1로 만들기” 문제를 해결하는 방법에 대해 작성해 보겠습니다. 이 문제는 주어진 정수 N을 1로 만들기 위해 필요한 최소한의 연산 횟수를 찾는 문제로, 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있습니다. 문제를 분석하고 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.

 

문제 URL: https://www.acmicpc.net/problem/1463

 

1. 문제 설명

백준 1463번 문제 “1로 만들기”는 주어진 정수 N을 1로 만들기 위해 최소한의 연산을 사용하는 문제입니다. 가능한 연산은 다음과 같습니다:

 

1. N이 3으로 나누어 떨어지면, 3으로 나누기.

2. N이 2로 나누어 떨어지면, 2로 나누기.

3. 1을 빼기.

 

각각의 연산을 통해 N을 1로 만드는 데 필요한 최소 연산 횟수를 구하는 것이 목표입니다.

 

2. 문제 접근법

이 문제를 해결하기 위해 동적 계획법을 사용합니다. 핵심 아이디어는 주어진 수 N에 대해 1로 만들기 위한 최소 연산 횟수를 미리 계산하고 저장하여, 그 값을 사용해 더 큰 수의 최소 연산 횟수를 쉽게 구하는 것입니다. 접근 방법은 다음과 같습니다:

 

1. DP 배열 사용: 최소 연산 횟수를 저장할 배열 dArr를 만듭니다. 여기서 dArr[i]는 숫자 i를 1로 만드는 데 필요한 최소 연산 횟수를 저장합니다.
2. 초기값 설정: N이 1인 경우 연산 횟수는 0입니다(dArr[1] = 0).
3. 반복적 계산: 2부터 N까지의 각 숫자 i에 대해 가능한 연산을 시도합니다. 각 연산 후의 숫자에 대해 이미 계산된 최소 연산 횟수에 1을 더한 값과 현재 값 dArr[i]를 비교하여 더 작은 값을 저장합니다.
4. 최적해 도출: 최종적으로 dArr[N]이 우리가 찾는 답이 됩니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# 정수 N을 입력 받습니다.
N = int(input())

# 최소 연산 횟수를 저장할 배열을 N+1 크기로 초기화합니다.
# 인덱스 0은 사용되지 않으므로 N+1 크기로 설정
dArr = [0] * (N+1)

# 1은 연산 필요 없음 (0번의 연산으로 가능)
dArr[1] = 0

# 2부터 N까지 순회하면서 최소 연산 횟수를 계산
for i in range(2, N+1):
    # 기본적으로 1을 빼는 연산을 가정
    dArr[i] = 1 + dArr[i-1]
    
    # 3으로 나누어 떨어질 때, 3으로 나누는 연산을 고려
    if i % 3 == 0:
        cnt = 1 + dArr[i // 3]
        # 3으로 나누는 것이 더 적은 연산을 필요로 할 경우 업데이트
        dArr[i] = min(cnt, dArr[i])
        
    # 2로 나누어 떨어질 때, 2로 나누는 연산을 고려
    if i % 2 == 0:
        cnt = 1 + dArr[i // 2]
        # 2로 나누는 것이 더 적은 연산을 필요로 할 경우 업데이트
        dArr[i] = min(cnt, dArr[i])

# N을 1로 만드는 데 필요한 최소 연산 횟수를 출력
print(dArr[N])

 

4. 코드 설명

위 코드는 주어진 N을 1로 만들기 위해 필요한 최소 연산 횟수를 동적 계획법을 사용하여 계산합니다. dArr 배열은 각 숫자에 대해 1로 만들기 위한 최소 연산 횟수를 저장하며, 반복문을 통해 1을 빼는 연산, 2로 나누는 연산, 3으로 나누는 연산을 고려하여 최소값을 갱신합니다.

5. Github으로 확인

 

coTest/BOJ/BOJ01_10_02_1463.py at main · pcy4196/coTest