본문 바로가기

알고리즘/백준93

[백준/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.
[백준/C,C++] 14889번: 스타트와 링크 www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 백준 단계별로 풀어보기 백트래킹 마지막 문제입니다. void dfs(int cnt, int number) { if (cnt == N / 2) { synergy(); return; } for (int i = number; i < N; i++) { M[i] = true; dfs(cnt + 1, i + 1); M[i] = false; } } 파라미터로 cnt와 number를 받아오는데 number를 받아오는 이유는 1, 2번이 팀인 경우.. 2021. 3. 6.

티스토리툴바