다이나믹프로그래밍2 [Java] 백준 1932번 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 문제 설명 크기가 N인 정수 삼각형 꼭대기에서 아래로 내려오면서 선택된 수의 합이 최대가 되는 경로 구하기 아래층 수는 현재층 대각선 왼쪽, 오른쪽만 선택 가능 삼각형의 크기는 1 이상 500 이하, 수는 0 이상 9999 이하의 정수 꼭 문제에 나와있는 그림처럼 정수 삼각형을 생각할 필요 없다. 우선 DP[N+1][N+1] (dp [][] = 각 자리의 수) 배.. 2020. 5. 16. [Java] 백준 14501 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 설명 N일 동안 상담을 완료해서 받을 수 있는 최대 수익 구하기. Ti = 상담하는데 걸리는 기간 Pi = 상담했을 때 받을 수 있는 금액 상담 중인 기간에는 다른 상담을 할 수 없다. 마지막 날부터 첫째 날까지 뒤에서 앞으로 거꾸로 생각하면 더 쉽게 풀 수 있는 문제 같다. dp [i] = i일부터 퇴사 날까지 얻을 수 있는 최대 이익이라고 하자. 상담일로부터 상담을 완료받기까지 걸리는 시간을 계산해 조건 (i + T [i] < N+1)을 만족시키는지 검사한다. N+1인 이유는 상담이 걸리는 시간이 상담을 시작한 날을 포함하기.. 2020. 5. 14. 이전 1 다음