9/4 Problem Solving

1106 호텔 (G4)

 

dp[i] = 고객 i명을 유치하기 위해 필요한 최소 비용

 

http://boj.kr/eda56c043fe04b94863a76278da6f9a4

 

 

2624 동전 바꿔주기 (G4)

 

dp[i] = i원을 만들 수 있는 방법의 수

 

http://boj.kr/0c30a754956b47ba8af519f7861feffb

 

 

12869 뮤탈리스크 (G4)

 

dp[a][b][c] = SCV 3개의 체력이 각각 a,b,c일 때, SCV들을 모두 파괴하는 데 필요한 최소 공격 횟수

 

SCV의 체력이 최대 60이므로 상태 공간을 60*60*60으로 설정한다. BFS를 돌리면서 최소 공격 횟수를 dp 테이블에 기록한다. 최종 정답은 모든 SCV가 파괴된 상태인 dp[0][0][0]이다.

 

http://boj.kr/af8d0db389f74dca84a7d2a4b4d4fb86

 

 

13144 List of Unique Numbers (G4)

 

투 포인터를 이용해서 right을 기준으로 잡고 구간을 늘리거나 줄여가면서 모든 구간을 탐색한다. 같은 수가 여러 번 등장하지 않는 경우에 대해서만 경우의 수를 세준다.

 

http://boj.kr/3d42f250d4134fcea395d297d7c9e675

 

 

2141 우체국 (G4)

 

마을들의 정보를 위치를 기준으로 정렬한다. 그리고 앞에서부터 누적해서 보면서 전체 사람수의 절반으로 나눠지는 순간 그 위치가 정답이 된다.

 

http://boj.kr/86c2b519c43741babd0de30241f83229