kthng

boj 2302 : 극장 좌석 쉬운 DP문제. 쉬운 DP는 그만 풀어도 되는데 손이 자꾸 가네... f(i) : vip가 없을 때 i번까지 자리를 바꿀 수 있는 경우의 수이렇게 두면1. i = 2 일 때 : f(i) = f(i - 1) + f(i - 2)2.1 f(i - 1) : i가 가만히 있는 경우2.2 f(i - 2) : i가 자리를 바꾸는 경우 vector에 0, vip1, vip2, ... vipM, N + 1을 담은 후결과값은 f(N + 1 - vipM) * ... f(vip2 - vip1) * f(vip1) 을 출력.

boj 1932 : The Triangle 전형적인 DP문제...sum[i][j] = max(sum[i - 1][j - 1], sum[i - 1][j]) + a[i][j]

boj 10164 : 격자상의 경로 많이풀어봤던 형식.O표시된 위치인 K의 값으로 y, x 좌표만 잘 해주면 되는데 여기서 실수 ㅜㅜDP로 해결.1. y = 0 or x == 0 이면 f(y,x) = 1.2. f(y,x) = f(y - 1,x) + f(y, x - 1).

boj 2513 : 통학버스 1. School을 기준으로 왼쪽 오른쪽은 서로 독립적.2. greedy로 가장 멀리사는 친구들부터 태우면 최단거리. 가장 멀리있는 친구부터 태우는게 최단거리라는건 직관적으로 이해되는데 어떻게 증명할 수 있을까?

boj 2512 : 예산 2개의 이분탐색으로 해결.1. 총 예산(M)을 벗어나지 않는 상한액의 최대값을 이분탐색.2. 상한액이 주어질 때의 예산합을 이분탐색으로 구현2-1. 요청비용들을 오름차순으로 정렬한 후 정렬된 요청비용배열 a에 대해 psum배열을 만들어줌 (psum[i] : i번째 요청까지의 금액)2-2. a[i]

boj 1374 : 강의실 그리디로 해결.1. N개의 pair(시작시간,종료시간) 을 sorting2. i - 1번째까지 가장 빨리 끝난 강의실에 i번째 강의를 추가 & 강의종료시간 갱신3. 강의할 수 있는 강의실이 없을 경우 강의실을 추가 이 방법이 최적값을 낸다는 건 직관적으로 알겠지만 증명은 어떻게하면 좋을까?