[백준] 1463 1로 만들기
맨 처음에는 0.1초가 나오도록 값을 입력받으면 바로 해결하는 프로그램을 짜려고 했는데, 이것은 조금 힘들 거 같아서 dp로 생각을 돌렸다. 맨 처음에는 1을 뺀 배열의 값을 참조해서 1을 더해주고 두번짼는 2로 나눠지면 2로 나눠진 배열에 1을 더해주고 마지막에는 3으로 나눠지면 3으로 나눠진 배열에 1을 더해준다. 고려하는 순서가 -1 , /2, /3인 이유는 큰 수를 나눌수록 가장 작은 횟수를 찾을 수 있기 때문이다. #include using namespace std; int arr[1000001]; int main() { int n; cin >> n; for (int i = 2; i = arr[i / 2] + 1) { arr[i] = arr[i / 2] + 1; } } if (i % 3 == 0..
2022.06.28