DP8 [백준 14501] 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net n=15라서 dfs와 dp모두 가능하다. 1번 접근 dfs 모든 경우의 수에 대해 최대 이익을 구하는 것이다. //브루트 포스 사용 #include #include #include #include using namespace std; int max_sum = -1; int n; struct Day { int during, val; }; vector tasks; void bruteforce(int cur_day, int val_sum, int val_cur) { if (cur_day == n + 1) { max_sum = max(max.. 2021. 7. 1. [백준 1948] 임계경로 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 위상정렬 + 역추적 문제이다. 문제이해가 어려웠으나 요약하면 1. 시작점->목적지까지 도달하는데 가장 오래 걸리는 시간 구하기 2. 1만큼의 시간이 소요되는 경로에 속한 도로들의 수 구하기 이다. 1분도 쉬지 않는다는 의미가 2라는 걸 이해하지 못했다... 1을 푸는 것은 위상정렬 + dp를 결합하면 어렵지 않게 해결할 수 있으나 문제는 2였다. 2에 대해 set으로 풀.. 2021. 6. 19. [백준 9184] 신나는 함수 실행 www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 바본가...출력 형식을 무시해서 이유없이 코드를 고쳤다.... 문제에서도 나와있지만: 재귀함수로는 어렵지 않지만 시간 초과가 발생하는 문제이다. 그럼 당연 dp지 라고 생각했지만 확신은 없었다 ㅋㅋㅋㅋㅋㅋ 3차원 배열..?진짜..? 진짜였다. 주어진 조건대로 1. 셋 중 하나라도 0이하 -> return 1 2. 셋 중 하나라도 20이상 -> w(20, 20, 20) 호출 3. a 2021. 1. 13. [백준 11051] 이항 계수 2 www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항계수를 구하는 문제이다. nCk = n!/k!(n-k)!이지만 n과 k가 1000까지 입력을 받기 때문에 저 식대로 계산하면 오버플로우가 발생한다. 그래서 파스칼의 삼각형을 사용하여 구해준다. 파스칼의 삼각형은 dp를 사용해서 구한다. nCk = dp[i][j] if j=0 or i=j then 1 else dp[i][j] = dp[i-1][j-1] + dp[i-1][j]로 식을 세울 수 있다. #include using namespace std; int dp[1001][100.. 2020. 12. 23. 이전 1 2 다음
