다이나믹_프로그래밍

[C++] 백준 1003번 피보나치 함수

시간 제한과 문제를 보더라도 쉽게 알 수 있는 다이나믹 프로그래밍 문제였다. 다이나믹 프로그래밍의 Bottom Up 방식으로 문제를 접근했다. F[0] = 1 0 F[1] = 0 1 F[2] = 1 1 F[3] = 1 2 . . . 즉, An = A(n-1) + A(n-2)임을 알 수 있다. 먼저 테스트 케이스 변수, 입력받는 정수 n이 있다. 그리고 pair 자료형의 배열을 사용해서 각 수마다 0이 나오는 횟수와 1이 나오는 횟수를 저장했다. pair 자료형은 {A, B}의 형태로 입력할 수 있다. make_pair(A, B)의 형태로도 입력할 수 있다. 첫번째는 first, 두번째는 second의 형태로 접근한다. 0과 1은 알 수 있으므로 미리 배열에 입력해 놓는다. 각 테스트 케이스마다 n을 입력..

[C++] 백준 9095번 1, 2, 3 더하기

처음 이 문제를 봤을 때 n이 작아서 백트래킹으로 문제를 풀려고 시도했다. 시간제한이 1초이므로 1억번의 연산이 가능한데 이 문제는 n이 아무리 커도 1억번을 넘지 않을거라 생각했다. 문제풀이 테스트 케이스를 입력받고 정수 n을 입력받으며 backTracking 메서드를 구현했다. 그리고 매 케이스마다 1, 2, 3 합의 개수를 나타내는 output 변수도 만들었다. 메인 함수에서는 간단하다. 매 케이스마다 결과값 output 변수를 0으로 초기화하고 backTracking 메서드를 1, 2, 3부터 시작한다. 이렇게 풀면 쉽게 맞출 수 있다. 그런데 이 문제는 백트래킹이 아닌 다이나믹 프로그래밍 문제였다. 다이나믹 프로그래밍이란? 다이나믹 프로그래밍, 동적 계획법은 큰 문제를 작은 문제로 쪼개어서 푸는..