본문 바로가기

퇴사 21

[백준 15486] 퇴사 2, C++ https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 본 문제는 퇴사와 조건은 똑같다. 차이는 입력의 크기가 퇴사는 15, 퇴사 2는 1,500,000으로 퇴사 소스코드로 퇴사 2를 풀 수 없다. 퇴사할 때까지 최대로 많은 이익을 얻으려면 퇴사 전까지 많은 이득을 얻어야 하기 때문에 큰 문제를 작은 문제로 해결할 수 있다. 그리고 계산의 반복이 있다. 따라서, DP로 문제 해결이 가능하다. 이 문제는 선택 여부에 따라 .. 2020. 2. 13.

티스토리툴바