[BOJ-JS] 12852번 - 1로 만들기 2

12852번: 1로 만들기 2 (acmicpc.net)

 

역으로 추적해나가는 방식으로 푼다. 코드를 짧게 줄이기 위해 오브젝트를 사용했는데, 배열로 풀어도 아이디어는 같다. 나는 오브젝트의 키값에 만들고자 하는 숫자를, 아이템에 해당 숫자에 도달한 경로를 배열로 넣어두었다.

숫자 i를 만드는 방법은

• i가 2로 나뉠 경우 i/2를 만드는 경로에 i 추가.
• i가 3으로 나뉠 경우 i/3를 만드는 경로에 i 추가.
• i-1을 만드는 경로에 i 추가.

위의 셋이 있는데, 이 중 제일 짧은 경로를 아무거나 하나 택해서 i를 만드는 경로로 사용하면 된다.

위와 같은 방식으로 2, 3, ..., n을 만드는 경로를 전부 구하면 끝.

n=+require('fs').readFileSync(0)
d={1:[1]}
i=1
while(i++<=n){
  a=[]
  if(i%2==0)a.push(d[i/2])
  if(i%3==0)a.push(d[i/3])
  a.push(d[i-1])
  x=a.sort((a,b)=>a.length-b.length)[0]
  d[i]=[i,...x]
}
console.log(d[n].length-1)
console.log(...d[n])