BOJ 1463: 1로 만들기

어제 백신을 맞아서 포스팅을 못 했는데, 오늘은 상태가 매우 괜찮아서 이렇게 왔습니다!

 

오늘의 문제 보시죠!

BOJ 1463: 1로 만들기

사실 이 문제도 예전에 스웨덴에서 있을 때 봤던 문제다. 그때는 알고리즘에 대한 기초 지식이 아예 없어서 어떻게 풀어야하는지 몰랐어서 굉장히 오랜 시간 고민하고 방황했었는데, 알고리즘 책도 읽고 다양한 문제를 풀면서 해결 방안을 바로 찾아냈다.

 

 

이렇게 간단한 코드로 해결한다.

우선, data라는 파일에 각 index별로 최소의 연산을 계산한다.

예를 들면 data[3]은 3을 만드는 데에 드는 연산의 수라고 할 수 있겠다.

이런 식으로 했을 때, 이미 있는 데이터보다 1을 더하거나, 2를 곱하거나, 3을 곱했을때 더 연산의 수가 적어지는 수로 업데이트한다.

 

good!