분류 전체보기351 [백준 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. [백준 1806] 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N R이 되면 합이 음수가 .. 2021. 6. 20. [백준 1072] 게임 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 투포인터 문제이다. 코드는 어렵지 않지만 투포인터를 떠올리긴 쉽진 않은거 같다 ㅠ while문을 돌리면 TLE가 발행한다. 이 문제의 또다른 포인트는 롱롱과 인트 범위라고 생각하는데 승률을 구하는 경우 소수점 아래는 버림하므로 먼저 100을 곱하고 시작하는 게 맞다. 이 경우 분자의 최댓값이 10^9이므로 100을 곱하면 INT 범위를 넘어선다. 따라서 N과 D는 롱롱이 되어야 한다. in.. 2021. 6. 20. [백준 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. 이전 1 2 3 4 5 6 ··· 88 다음