반응형 동적 계획법1 [BOJ 1463] 1로 만들기 (2가지 풀이/DP/BFS) (C++) www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 구현 방법 (DP 풀이) 이 문제는 전형적인 DP(Dynamic Programming) 문제입니다. DP문제를 해결하는 순서는 다음과 같습니다. 테이블 정의하기 점화식 찾기 초기값 정하기 이 문제에서 위 순서를 따라 답을 찾아보겠습니다. 테이블 정의하기 이 문제에서 테이블은 "D [i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값"이라고 정의할 수 있습니다. 테이블이란 이 문제에서 사용할 배열과 배열에 들어가는 각 값들의 의미입니다. 즉, 배열 d의 i번째에 들어가는 값은, i를 1로 만들기 위해 필요한 연산 .. 2021. 5. 1. 이전 1 다음 반응형