본문 바로가기

동적계획법27

[백준/C,C++] 1904번: 01타일 www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 점화식만 찾아낸다면 정말 간단한 문제입니다. N이 0일 경우 만들 수 있는 타일의 개수는 0개입니다. 1일 경우 1개, 2일 경우 2개라고 문제에 나와 있죠. 3은 011, 100, 111로 3개입니다. 4의 경우는 5개로 문제에 나와 있습니다. 해를 쭉 나열해보면 0, 1, 2, 3, 5인데, 피보나치 수열과 굉장히 유사합니다. 작은 문제를 쌓아 큰 문제를 푸는 상향식(Bottom-up) 동적 계획법을 이용하면 쉽.. 2021. 3. 7.
[백준/C,C++] 9184번: 신나는 함수 실행 www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net DP만 이용한다면 쉽게 풀 수 있는 문제입니다. 문제의 점화식이 다 주어지므로 그대로 코딩하시면 됩니다. #include using namespace std; #define MAX 21 int DP[MAX][MAX][MAX]; int w(int a, int b, int c) { if (a 20) return w(20, 20, 20); if (DP[a][b][c]) return DP[a][b][c]; if (a < .. 2021. 3. 7.
[백준/C,C++] 1003번: 피보나치 함수 www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 백준 단계별로 풀어보기 동적 계획법 1 첫 번째 문제입니다. 흔히 DP라고 부르는 동적 계획법(Dynamic Programming)은 문제를 작은 문제로 나누어 해답을 기억해뒀다가 중복되는 문제에 재활용하는 기법을 의미합니다. 피보나치 함수의 경우 fibonacci(3) = fibonacci(2) + fibonacci(1)인데 fibonacci(2)는 다시 fibonacci(1)을 호출합니다. 이렇게 중복된 부분이 생기고 입력값이 커질수록 중복되는 부분은 기하급수적으로 늘어납니다. 그림을 보시면 중복된 일을.. 2021. 3. 7.

티스토리툴바