9/7 Problem Solving

1099 알 수 없는 문장 (G3)

 

dp[i] = i번째 문자까지 만들 수 있는 최소 비용

 

http://boj.kr/2f180cfc6e6f445b98191f366c8a98a6

 

 

1082 방 번호 (G3)

 

dp[i] = i원을 사용해서 만들 수 있는 가장 큰 방 번호

 

http://boj.kr/a6889080f221488e92ca74fea010ec92

 

 

2248 이진수  찾기 (G3)

 

이항계수의 성질을 이용해서 범위 안의 combination 값들을 미리 계산해준다. 그리고 가장 높은 자리부터 내려가면서 i-1개 자리에서 L개 이하의 1개 배치될 수 있는 모든 경우의 수보다 현재 I가 크다면 현재 자리에 1을 넣는다. 그렇지 않다면 0을 넣는다. 이런식으로 I번째 이진수를 구할 수 있다.

 

http://boj.kr/20e6b7231f8d4784a5f7f76f2a634b68

 

 

2513 통학버스 (G3)

 

학교 위치 기준으로 왼쪽, 오른쪽의 아파트들의 위치를 따로 담은다음 각각 가장 먼 곳~가까운 곳 순서대로 정렬한다. 그리고 가장 먼 곳부터 처리하는게 이득이므로 그리디하게 총 이동거리를 계산해주면 된다. 아이디어는 간단한데 구현이 조금 생각해야 되는게 있다.

 

http://boj.kr/e6689e725f9240bb99429fc3affb7867

 

 

2608 로마 숫자 (G5)

 

케이스 분류를 정확하고 빠짐없이 잘해서 구현하면 된다.

 

http://boj.kr/65c3689d3b884d859e593974685160e0