본문 바로가기

c++104

[백준/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.
[백준/C,C++] 14888번: 연산자 끼워넣기 www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 연산자의 순서를 바꿔가며 가장 큰 값과 작은 값을 출력해주면 되는 문제입니다. void dfs(int cnt) { if (cnt == n - 1) { calc(); } for (int i = 0; i 0) { operators[i]--; stack.push_back(i); dfs(cnt + 1);.. 2021. 3. 6.

티스토리툴바