[백준] 1463 - 1로 만들기
문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 해결 과정 단계별로 풀어보기 중 동적 계획법(Dynamic Programming)에 나온 문제라서 우선 동적 계획법을 시도했다. 당시에는 구하고자 하는 수에서 부터 1로 계산해가는 방식을 사용하려고 했는데 구현 과정에서 막혔다. BFS를 이용해서 처음 n에 도달하면 탐색을 종료하는 방법을 떠올리고 시도해 보았지만 BFS를 구현한 적이 없어서 실력 부족으로 역시 실패했다. 결국 생각을 바꿔 동적 계획법으로 1부터 n까지 계산해가며 쌓아올리는 방식으로 구현해냈다. 아래는 성공한 결과물이다. #include inline int min(int a, int b) {return a..
공부한 것들/알고리즘
2020. 2. 5. 10:09