[백준] 1463번 - 1로 만들기

문제 링크 : https://www.acmicpc.net/problem/1463

문제 탐색하기

1) 문제 분석

X가 3의 배수면 3으로 나눈다.
X가 2의 배수면 2로 나눈다.
두 가지 경우가 다 아니면 1을 뺀다.
연산을 사용하는 횟수의 최솟값을 구하자.

2) 가능한 시간복잡도

(1) 입력 처리 : 단일 입력 -> O(1)

(2) DP 테이블 채우기 : N까지 채우기 -> O(N)

(3) 연산횟수 출력하기 : 단일 출력 -> O(1)

(4) 전체 시간복잡도 : O(N)

3) 알고리즘 선택 이유

이 문제는 1부터 N까지의 숫자에서 반복적으로 최소 연산 횟수를 구해야 하는 문제이다.
- 같은 숫자에 대해 최소 연산 횟수를 여러 번 계산할 수 있다. (예시 : 10의 경우 5를 여러 경로에서 다시 계산)
- 최적의 해는 작은 문제들의 최적 해로부터 구성된다.
- 이미 계산한 숫자의 최소 연산 횟수를 DP 테이블에 저장해두고 계산할 수 있다.
- Bottom-Up 방식이 더 직관적이고 메모리 관리도 쉽다.
따라서 DP 알고리즘을 선택했다.

잠깐! Dynamic Programming(DP, 동적 프로그래밍)에 대한 간단한 설명, 그리고 관련 예시 문제는 여기를 참고하자.

코드 설계하기

1. 실행 구조

1) 입력 처리

X를 입력 받는다.

2) 연산 횟수 구하기

연산 횟수 변수 선언
연산 횟수 구하는 함수 선언
- 초기 dp 선언 및 초기화
- 2부터 연산 횟수 계산 시작 (1은 이미 1이므로 2부터 시작)
- 입력한 수의 연산횟수 반환

3) 결과 출력

결과 출력

2. 고민이 되었던 부분

JavaScript

dp[i] = Math.min(
    (i % 3 === 0) ? dp[i / 3] : Infinity,
    (i % 2 === 0) ? dp[i / 2] : Infinity,
    dp[i - 1]
) + 1;

: 점화식을 구하는 부분이 해당 문제에 있어서 메인 포인트였다. 최소 연산 횟수를 구해야 하므로, 현재 숫자를 만들 수 있는 3가지 경우의 수(3으로 나누기, 2로 나누기, 1 빼기) 중에서 이전에 계산한 값들을 재활용하는 방식으로 점화식을 구성해야 했다. 처음에는 3과 2로 나누는 연산이 항상 가능한 줄 알고 단순히 세 가지 경우를 무조건 비교하려 했지만, 조건문을 통해 나눌 수 있을 때만 선택지로 포함해야 한다는 점을 늦게 깨달아 점화식을 수정하게 되었다.

또한, DP의 초기값을 dp[1] = 0으로 두어야 하는 이유(이미 1이므로 연산 필요 없음)도 다시 한번 점검하게 되었고, 나머지 값들은 dp[1]을 기준으로 쌓아가는 구조로 설정해야 하는 점도 중요하게 느꼈다.

정답 코드

JavaScript

// 사용 언어 : Javascript

// 입력 처리
const fs = require('fs');
let input = Number(fs.readFileSync('/dev/stdin').toString().trim().split("\n"));

// 연산 횟수 변수
let count = 0;

// 연산 횟수 구하는 함수
function getCountMakeOne(size) {   

	// dp 선언 및 초기화
    const dp = [];
    dp[1] = 0; // 1은 연산횟수 0

	// 2부터 연산 횟수 계산 시작
    for (let i = 2; i <= size; i++){
        dp[i] = Math.min(
            (i % 3 === 0) ? dp[i / 3] : Infinity,
            (i % 2 === 0) ? dp[i / 2] : Infinity,
            dp[i - 1]
        ) + 1;
    }
	
    // 입력한 수의 연산횟수 반환
    return dp[size];
}

// 결과 출력
console.log(getCountMakeOne(input));

마무리하며

처음 이 문제를 접했을 때 단순히 빙고판에서 숫자를 지우는 과정만 생각했지만, 조금만 더 들여다보니 ‘3줄이 완성될 때 빙고를 외친다’는 조건이 생각보다 중요한 핵심임을 깨달았다. 숫자를 지우는 것 자체는 단순했지만, 가로, 세로, 대각선에서 선이 언제 몇 개가 만들어지는지를 관리하는 것이 진짜 문제 해결의 본질이라는 점을 뒤늦게 알게 되었다.

개인적으로 이번 문제를 풀면서, 문제의 본질을 파악하는 힘이 얼마나 중요한지 다시 한 번 느꼈다. 코드로 구현하는 것은 결국 내가 문제를 어떻게 이해했는지의 반영이기 때문에, 문제를 단순히 ‘코드로 푼다’는 생각보다는, 상황을 정확히 이해하고 그 구조를 코드로 옮기는 과정임을 더 체감하게 되었다.

이번 문제를 통해 새삼 깨달은 건, 정답을 맞추는 것이 끝이 아니라는 점이었다. 문제를 이해하고 나만의 방법으로 풀어내는 과정 자체가 중요했고, 무엇보다 더 나은 방향을 고민하는 습관이 문제 해결력의 일부라는 걸 경험할 수 있었다. 앞으로도 단순히 빠르게 푸는 것이 아니라, 내가 구현하는 코드가 ‘좋은 코드’인지 계속 고민하고 점검하는 개발자가 되고 싶다.

최근 글