[백준 1463] 1로 만들기 - 다이나믹프로그래밍 ( 자바스크립트+ 코드 진화과정)

1로 만들기

1보다 큰 정수 n이 주어질 때,
1. 3으로 나누어 떨어질 때 3으로 나누거나
2. 2로 나누어 떨어질 때 2로 나누거나
3. 1을 빼거나

3가지 연산을 통해 n을 1로 만들 수 있는 최소의 연산 수를 구하라.
라는 문제이다.

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

맨 처음 최소 연산 수라는 키워드를 놓치고 단순 if 문으로 구현 하였더니, 당연히 틀렸다.

왜냐!

n 이 10일 때 if 문을 통해 3가지 연산을 수행하면

10 => 2로 나눈다 (5) => 1을 뺀다 (4) => 2로 나눈다 (2) => 2로 나눈다 (1)

총 4번이라는 결과값이 출력되는데,

사실 최소 연산값은

10 => 1을 뺀다 (9) => 3으로 나눈다 (3) => 3으로 나눈다 (1) 로 연산을 끝내는

3이 정답이기 때문이다.

최소의 연산 값을 구하기 위해서는 모든 가능한 연산을 다 수행하여 1이 나올때 연산을 중지하는 방법으로 다이나믹 프로그래밍을 적용하는 것이 문제 출제자의 의도라는 것을 파악하였다.

풀이

단순히 최소의 연산 과정만을 보여주면 됨으로 딕셔너리 형태의 자료구조를 활용하여 연산값들을 기록해 두려 하였다.

연산 횟수를 t로 두고 t번째 연산에 해당하는 결과 값을 배열로 저장하여 다이나믹프로그래밍을 구현하였다.

알고리즘 설계를 간략히 그림으로 표현하면 이러하다.
각 계산 값을 자료구조에 저장하고 이 중 1이라는 결과값이 나올 때! 루프를 중단하여 t를 반환한다.
(실제로 코드 작성 전 그림을 도식화해서 이해한 다음 코드를 짜는게 좋다하여 습관을 들이고 있다.)

첫번째 통과 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const n = Number(input[0]);

let t = 0;
let dict = {
    0: [n]
}

while (true) {
    t ++;
    dict[t] = [];
    for (let n of dict[t-1]) {
        if (n == 1) return console.log(t-1);
        if (n == 0) continue; 
        dict[t].push(n % 3 == 0 ? n / 3 : 0);
        dict[t].push(n % 2 == 0 ? n / 2 : 0);
        dict[t].push(n-1);
    }
}

그림 대로 코드를 작성한 결과 만약 3으로 나누어지지 않거나, 2로 나누어지지 않는 경우 해당 메모리에 0을 넣어 계산되지 않는 예외 값을 넣어 두었다.

그러니 잘 돌아가고 통과하긴 하더라, 허나 0을 넣는 방법은 불필요한 메모리 공간을 다수 차지하게 되고 필요없는 연산을 실행하게 되어 비효율적인 코드라고 판단되었다.

실제로 백준 메모리와 실행 시간을 보면

꽤 느리고 비효율적이라고 생각이 드는 수치이다.

코드 효율화 작업

if 문을 사용해서 루프를 돌리면, 3으로 나누어질 때 2을 수행하지 않거나 1을 빼지 않는 문제가 발생하고, 삼항연산자를 이용하니 n%3 같은 조건이 false일때 0을 대입하는 방법 외엔 딱히 좋은 방법이 생각나지 않았다.

그러다 문득 ||, && 와 같은 and, or 연산자의 활용으로 조건에 따른 코드 수행이 기억이 났다. 자바스크립트의 특징적인 문법이라 참 좋다.
and, or에 경우 둘을 합쳐 하나의 조건으로 만드는데

• || (or 연산자)
  -> 앞에 구문이 falsy 할 경우 뒤 구문 실행
  -> 앞에 구문이 truethy 할 경우 뒤 구문 실행하지 않음
  : 맨처음이 true이면 굳이 뒤를 실행하지 않아도 true라고 확정이 됨으로 자바스크립트는 실행하지 않음, 그 반대인 경우 뒤가 true인지 false인지 확인해야함으로 실행이 됨

• && (and 연산자)
  -> 앞에 구문의 반환값이 truthy 할 경우 뒤 구문 실행
  -> 앞에 구문의 반환값이 falsy 할 경우 뒤 구문 실행하지 않음
  : 앞이 false이면 and연산자에 의해 false가 확정됨으로 자바스크립트가 실행하지 않음, 그반대에 경우엔 뒤를 확인해야 and의 결과값이 true인지 false인지 알기 때문에 확인해야함.

예시)

n % 3 == 0 && dict[t].push(n / 3);
// 앞에 조건문이 true 이면 실행
n % 2 == 0 || dict[t].push(n / 3);
//앞에 조건문이 false인 경우 실행

최종 결과 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const n = Number(input[0]);

let t = 0;
let dict = {
    0: [n]
}

while (true) {
    t ++;
    dict[t] = [];
    for (let n of dict[t-1]) {
        if (n == 1) return console.log(t-1);
        n % 3 == 0 && dict[t].push(n / 3);
        n % 2 == 0 && dict[t].push(n / 2);
        dict[t].push(n-1);
    }
}

논리 연산자를 활용하여 기존에 불필요한 0을 자료구조에 추가하는 과정을 없애고 코드를 간소화 하였다. 이 결과 dict 자료구조 내에 연산이 불가능한 경우 메모리를 차지하거나 구문을 실행하는 경우가 사라지고 코드 실행시간과 메모리를 단축시킬 수 있었다.

메모리와 실행시간 모두 거진 50% 이상 단축된 모습

끝!