기말 고사 준비(기업투자)

[초등부] 기말 고사 준비

정보 올림피아드 문제에서 가장 쉽게 접할 수 있는 문제는 최적해를 구하는 것이다. 최적해를 구하는 것은 발생할 수 있는 모든 경우를 고려한 후 답을 구할 수 도 있지만, 수행 시간 문제가 발생한다. 이번 문제에서는 최적해 문제의 해결에 접근하는 방법을 학습

하고자 한다.

문제 ( 난이도 ★★★☆☆ )

인표는 기말 고사를 앞두고 있다. 지난 중간고사 때 감기몸살로 공부를 제대로 하지 못해 성적이 저조했다. 그래서 인표는 기말고사를 더욱 중요하게 생각하고 있다. 그러나 불행히도 인표에게 주어진 시간은 그리 많지 않다. 인표는 자신에게 주어진 시간을 최대한 효율적으로 사용하여 기말고사에서 최대의 효과를 보려고 그 동안의 경험과 친구들의 조언을 토대로 다음과 같은 표를 만들어 보았다.

투자시간	수학	영어
1	10	40
2	30	50
3	50	70
4	80	85

위의 표에 따르면 인표가 1시간 수학공부를 하면 수학에서 10점을 맞고 영어를 4시간 공부하면 성적을 85점 맞을 수 있다. 만약 인표에게 주어진 시간이 4시간이라면 인표는 4시간을 효율적으로 분배하여 수학 + 영어 점수가 최대가 되게 해야 한다. 위의 예에서는 수학 3시간 영어 1시간을 공부해서 총점 90점을 맞는 것이 최선의 방법이다.

인표에게 주어진 시간이 정해져 있고, 과목수와 각 과목을 공부하는 데 투자한 시간별로 얻을 수 있는 점수가 주어질 때 인표가 최대 총점을 맞을 수 있는 시간 분배 방식과 최대 총점을 출력하는 프로그램을 작성하라. 단 한 과목에 대해 시간을 나누어 투자할 수 없다(예 : 영어1시간 + 영어3시간과 같이 할 수 없다). 프로그램의 이름은 “dynamic"으로 한다.

입력 형식

입력 파일명은 "Input.txt"로 한다. 입력 파일의 첫째 줄에는 투자시간과 과목수가 주어진다. 둘째 줄부터는 투자시간과 각 과목별 얻을 수 있는 점수가 주어진다. 투자 시간은 100시간을 넘지 않으며 과목 수는 최대 20개이다.

출력 형식

출력 파일명은 "Output.txt"로 한다. 출력 파일의 첫째 줄에는 각 과목에 투자한 시간을 빈칸으로 구분하여 출력하고 둘째 줄에는 최대 총점을 출력하라

입력과 출력의 예 1

입력의 예(Input.txt)

4 2

1 10 40

2 30 50

3 50 70

4 80 85

출력의 예(Output.txt)

3 1

90

입력과 출력의 예 2

입력의 예(Input.txt)

3 3

1 10 40 30

2 30 50 57

3 50 70 67

출력의 예(Output.txt)

0 1 2

97

[초등부] 기말 고사 준비

문제의 배경 및 관련 이론

정보 올림피아드를 준비하는 사람이라면 동적계획법(Dynamic programming : 다이나믹

프로그래밍)에 대해서 조금은 들어 보았을 것이다. 정보 올림피아드는 13회 대회부터 매

년 세 문제 중 한 문제는 동적계획법 문제를 출제하고 있다. 최적해를 구하는 문제를 쉽고 깔끔해서 풀기 위해서는 동적계획법의 개념 및 적용할 수 있는 문제에 대해 알고 있어야 하며 동적계획법을 이용한 풀이과정에 대해서도 필히 익혀 두어야 한다.

동적계획법은 작은 문제들의 해를 배열에 저장한 다음 그것들을 순환적(recursive)인 성질을 이용하여 결합해 큰 문제의 해를 구하는 방식이다. 동적 계획법의 특징을 살펴보면

다음과 같다.

1. 동적계획법은 해를 저장하는 배열을 사용한다(테이블).

같은 문제에 대한 답을 여러 번 구할 필요가 없는 이점이 있다. (분할 정복과 다른 점)

2. 동적계획법은 순환적인 성질을 이용한다.

3. 동적계획법은 점화식을 사용한다.

위 세 번째 특징에서 점화식은 큰 문제와 작은 문제간의 관계를 표현하는 식이다. 큰 문제를 풀기 위해 작은 문제의 해를 미리 구해 놓아야 한다는 뜻이다. 동적계획법을 이용한 문제의 예는 피보나치 수열, 펙토리얼 수 구하기 등 아주 유명한 문제에서부터 최단거리 찾기 등 다양하게 찾아볼 수 있다. 그러나 동적계획법이 확실히 유용한 알고리즘 설계기법이긴 하지만 어떤 문제에든지 적용할 수 있는 것은 아니다. 동적

계획법이 성립하기 위해서는 최적화 원리 (Principal of optimality) - 한 문제에 대한 해가 최적이면 그 부분을 이루는 부분 문제들의 해도 최적이다-가 성립해야 한다.

최적화의 원리의 예를 다음과 같이 볼 수 있다. 아래 그림에서 보듯이 A, B, C라는 장소가 있고 A에서 B를 거쳐 C로 가는 최선의 방법을 찾았다면 그 방법은 반드시 A에서 B로 가는 최선의 방법일 것이고 B에서 C로 가는 최선의 방법일 것이다. 이처럼 동적계획법에 적용할 수 있는 문제는 찾으려는 해의 부분해도 최적이 되는 경우이다.

문제 해설

동적계획법의 전형적 문제

이번 문제는 전형적이면서도 유명하기도 한 동적계획법 문제이다. 기출 문제와도 유사한 형태이다. 동적 계획법의 기본기를 다질 수 있는 좋은 문제이므로 꼭 공부해 두는 것이 좋다. 동적계획법 문제를 풀기 위해서는 점화식을 만들어야 한다. 일단 점화식을 만들기 위해 문제를 단순화 시켜보자.

현재 t 만큼의 시간이 있고, 공부할 과목이 하나 있다고 가정해 보자. 그렇다면 최대의 점수를 얻기 위해서는 모든 시간을 그 과목 공부에 전부 투자해야 할 것이다. 이것이야 쉬우니까 별 문제 없다. 그럼 사고를 확장시켜서, 과목이 둘 있다고 가정해 보자. 이 경우도 그리 어렵진 않다. 과목 A에 3시간, 과목 B에 4시간 투자하는 것을 (3, 4)라고 표현하자.

현재 5시간이 주어졌다면

(0, 5)

(1, 4)

(2, 3)

(3, 2)

(4, 1)

(5, 0)

이 다섯 가지의 경우 중 가장 점수가 높은 방법을 선택하면 될 것이다. 그럼 이제 모든 문제 해결은 끝났다. 단지 두 과목만을 봤을 뿐인데 이런 결론을 지을 수 있는 이유는 동적계획법을 적용할 수 있는 문제이기 때문이다.

과목이 세 개 이상이라면, 우리는 그 과목들을 2개인 것으로 축소해서 생각하면 된다. 예를 들어 과목이 4개 있고 5시간이 주어져 있으면, 첫 번째, 두 번째, 세 번째 번째 과목을 과목 B라고 하면 (A, B)의 순서쌍은

(0, 5)

(1, 4)

(2, 3)

(3, 2)

(4, 1)

(5, 0)

로, 위에서 본 것과 동일한 형태이다. (3, 2)의 경우는 과목 B에 2시간을 투자하고 나머지 세 과목에 3시간을 투자한다는 것이다. 세 과목에 대해서 시간을 어떻게 투자할 것인가의 문제는 이미 계산이 되어져 있다. 동적 계획법의 특성상 이전 단계의 해는 이미 구해 져

있기 때문이다. 따라서 큰 문제도 작은 문제로 바꿔서 볼 수 있게 된다. 지금까지의 이야기를 정리해 보면 다음과 같다.

C[i, j]가 i의 과목들에 j시간을 투자했을 때의 최대 점수라 하자. 이때 다음과 같은 경우들이 있다.(a[i, j]는 입력으로 주어진 i번째 과목에 j시간을 투자했을 때의 과목 총점)

i과목에 0시간을 투자하는 경우 :

C[i, j] = C[i-1, j] + a[i, 0]

i과목에 1시간을 투자하는 경우 :

C[i, j] = C[i-1, j-1] + a[i, 1]

i과목에 2시간을 투자하는 경우 :

C[i, j] = C[i-1, j-2] + a[i, 2]

i과목에 3시간을 투자하는 경우 :

C[i, j] = C[i-1, j-3] + a[i, 3]

...

i과목에 j시간을 투자하는 경우 : C[i, j] = C[i-1, 0] + a[i, j]

이 j+1가지 경우 중에 가장 최대의 총점을 얻는 경우를 계산하면 된다. 위의 경우들을 일반화 시켜보면,

C[i, j] = max {C[i-1, j-k] + a[i, k]} (단, k는 0≤k≤j인 정수)가 된다. i가 1인 경우는 과목이 하나인 경우이므로 C[1, j] = a[1, j]가 된다.

-내 생각-

그냥 기업투자 문제랑 다를게 없습니다. 아마 한번쯤은 들어보셨을 문제입니다.(DP문제 중 가장 유명한 문제인 LIS와 동급으로 유명한 문제라고 생각됩니다.)

사실 저도 어려워요 zzz

소스파일 :

기말고사 준비(기업투자).cpp