1563. 개근상

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA 
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO 
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA 
LAOO LAOA LAAO

으로 총 43가지이다.

한 학기는 N일이다. N이 주어졌을 때, 개근상을 받을 수 있는 출결정보의 개수를 세는 프로그램을 작성하시오.

4

43

1. 접근

하루에 할 수 있는 출결은 세 가지이다. 몇일 동안 출결할지 정해지고, 상을 탈 수 있는 조건이 주어졌을 때 조건을 만족하는 출결순열의 경우가 총 몇가지 인지 구해야 한다.

조건이 없다면 3 ^ N 가지의 경우가 있겠지만, 조건은 지각은 한번만 가능하고, 결석은 이틀까지만 연속으로 가능하다.

이틀 결석하고 출석하고, 이틀 결석하고 출석하는 경우가 가능하다는 뜻이다.

어떤 방법을 써야 모든 경우를 잘 셀 수 있을까?

2. 풀이

직관적으로 가능한 모든 조합을 확인하는 방법이 있겠다. 하지만 N은 최대 1000일 이므로, 3 ^ 1000 개의 조합을 확인하기엔 시간이 모자르다.

그러면 어떤 규칙을 통해 모든 조합을 확인하지 않아도 될까?

당장에 어떤 수학적인 규칙은 보이지 않으므로,

가능한 경우를 계속 늘려가면서 세버리는 다이나믹 프로그래밍을 쓰기로 하자.

그러면 조건을 잘 활용해야 한다. 지각의 횟수는 계속 누적되고, 결석은 누적되지 않는다는게 특징이다.

배열은 다음과 같이 정의한다.

DP[지금까지 출결한 날][지금까지 지각한 횟수][지금까지 연속으로 결석한 횟수] = DP[day][cnt1][cnt2]

= 지금까지 상황이 이러저러 할 때, 최종적으로 조건을 만족하는 경우의 수

당연히 문제의 답은 DP[0][0][0]에 있을 것이다.

N = 4 라면 DP[4][1][2] = 1이다. 반대로 DP[4][2][2] = 1이다.

DP배열을 갱신해줄 함수는 다음과 같다.

func(int day, int cnt1, int cnt2) = DP[day][cnt1][cnt2] 를 잘 계산해준다.

함수가 종료될 기저사례는 무엇이 있을까

우선 cnt1이 2까지 차버렸거나, cnt2가 3까지 차버린 경우다. 이러면 앞으로 무슨 출결을 해도 상을 못받는다

= return 0

우여곡절로 N일 까지 도착했다면, 앞의 기저사례는 통과했다는 뜻이니까 상을 받을 수 있다.

 = return 1

내일의 출결은 세가지 가능하다.

1. 잘 출결한다 -> func(day + 1, cnt1, 0) 지각은 누적제이고, 결석은 사라진다.

2. 지각한다 -> func(day + 1, cnt1 + 1, 0) 지각은 누적제이고, 결석은 사라진다.

2240. 자두나무

7 2
2
1
1
2
2
1
1

6

1. 접근

두 나무 중에 내 위치를 w번 갈아탈 수 있다. t초 동안 자두는 t개 떨어지며,

매 초마다 두 나무 중에 자두를 떨궈줄 나무가 입력으로 주어진다.

t번 갈아탈 수 있다면 모두 받아먹을 수 있겠지만, w번으로 갈아탈 수 있는 기회가 한정된다.

그러면 우리는 어떤 전략으로 임해야 최대한 많은 자두를 받아먹을 수 있을까?

2. 풀이

전략을 생각해내기 보다 걍 컴퓨터에게 계산을 시키기로 하자.

심플함이 잘 팔리므로, 다이나믹 프로그래밍을통한 메모이제이션으로 모든 경우를 빠르게 확인해버리는 것이다.

얼마나 빠른지가 중요할텐데, 시간은 DP 배열의 크기에 비례한다.

문제의 변수는 세가지다 : 시간, 위치를 바꾼 횟수, 나의 위치

무언가 전략이 있다면 (최대 갯수가 세 가지 변수보다 적은 변수로 결정난다면) 더 작은 배열로 가능하겠지만, 나는 생각이 안나므로,

삼차원 배열로 DP 배열을 정의하도록하자.

DP[현재시간][현재 나의 위치][자리바꾼 횟수] = 현재 상황이 이러저러 할 때, 지금 상황부터 받아 먹을 수 있는 자두의 최대 갯수

정의 덕분에 함수 정의도 술술 풀린다.

func(int now, int pos, int cnt) = DP[now][pos][cnt] 를 계산해주는 함수.

나머지 할 일은 점화식을 세워주기만 하면된다. 계산은 컴터가 다 해준다.

자두를 받아먹는 경우는 다음 여섯가지로 나눠진다.

1. 현재 시간에 나의 위치와 자두가 떨어질 위치가 같다.

1-1 위치변경의 기회가 남았다.

1-1-1. 그래서 자리를 바꾸지 않고 1개 챙길 수 있다.

1-1-2. 자리를 바꾸고 후일을 도모한다.

-> max(func(now + 1, pos, cnt) + 1, func(now + 1, pos ^ 1, cnt + 1));

1-2 자리바꿈의 기회를 다 써버려서 가만히 있는다 -> 1개 챙긴다.

-> func(now + 1, pos, cnt) + 1;

2. 현재 시간에 나의 위치와 자두가 떨어질 위치가 다르다.

2-1 위치변경의 기회가 남았다.

2-1-1. 그래서 자리를 바꾸지 않고 후일을 도모한다.

2-1-2. 자리를 바꾸고 1개 챙긴다.

-> max(func(now + 1, pos, cnt), func(now + 1, pos ^ 1, cnt + 1) + 1);

2-2. 자리바꿈의 기회를 다 써버려서 가만히 있는다 

-> func(now + 1, pos, cnt);

케이스별로 함수를 호출해주고, 정답을 꾸려나가면 된다.

기저사례는 now가 T를 넘어가버리는 경우로, 정의에 따라 0을 리턴해야한다.

케이스를 더 효율적으로 나눌 수도 있겠다.

3. 코드

1102. 발전소

3
0 10 11
10 0 12
12 13 0
YNN
3

21

1. 접근

p개 이상의 발전소를 규칙에 따라 모두 가동시켜야 한다.

발전소를 가동시킬려면 기존에 가동되고 있던 발전소가 필요하고, 발전소끼리 가동시키는 비용이 각기 다르다.

p개 이상의 발전소를 가동시키는데 드는 총 비용의 합이 최소가 되는 경우는 무엇일까?

2. 풀이

p개 이상이란 뜻을 생각해보자.

p + 1, p + 2, ... n 개를 가동시키는데 드는 최소비용이 p개 보다 작을 경우가 있다는 말일까?

있다고 쳐보자, 그러면 p + x 개를 가동시키는 방법은 p개를 가동시키는 방법과 다른 부분이 존재한다는 뜻이다.

완전한 부분집합이라면 당연히 p개가 더 작다.

하지만 다른 부분으로 이어지는 경로의 p개 까지의 경로가 당연히 p + x 보다 짧다!

따라서 우리는 문제를 괜히 꼬아서 낸거라고 생각하고 p개로 고정시키자.

일단 -1을 출력해야 하는 상황을 생각해보자면,

하나라도 켜져 있으면 전부 가동시킬 수 있으니까, 전부 고장난 상태라면 -1이다.

마찬가지로 이미 p개보다 많이 켜져있다면 보나마나 0이다.

한편 이 문제를 그리디적으로 풀 수 있을까?

당장에 가동중인 발전기로 가동시킬 최소비용을 선택해 나가는 것이다.

하지만 최소비용이 같을 경우, 나머지 부분 문제는 당연히 가동중인 발전기 종류가 달라지므로 그리디적으로 풀 수 없다.

그러면 다 계산해보자!

n개의 발전기가 있으므로, 각 발전기가 가동중인 상태를 비트로 나타내기 위해선 n + 1 개의 비트가 보장되어야 한다.

그러면 DP[2 ^ N]의 배열을 잡자. 이 배열은 현 가동 상태에서 추가로 발생하는 비용을 담는다.

우리의 답은 DP[처음의 가동 상태]에 있을 것이다.

이제 계산을 해줄 함수를 정의해보자.

func(int num, int stat) = num개를 가동 중이고, 가동상태는 비트로 stat일때, 추가로 발생하는 비용

계산식을 어떻게 만들어야 할까?

n=3이고 현 상태가 100이라 해보자(1발전기가 가동중이다)

먼저 가동중인 발전기를 찾아야 한다. 그 다음으로 고장난 발전기를 찾아야한다.

이 후 가동시키려면 당장의 비용이 발생하니까, 식은 다음과 같다.

dp[stat] = min(dp[stat], func(num + 1, stat | (1 << 고장난 발전기)) + cost[가동 발전기][고장 발전기]

기저사례는 num이 p까지 도달해버린 경우로, func(p, stat) 은 당연히 정의에 따라 0을 반환해야 한다.

메모이제이션을 통해 시간이 단축된다.

3. 코드

4. 후기

메모이제이션을 이상하게 해서 한참을 해맸다. 기초의 중요성 ㅎ

1562. 계단 수

10

1

1. 접근

계단수는 인접한 자리수의 차이가 모두 1인 수를 일컫는다. 987654321 같은 수가 대표적이다.

쉬운 계단수 문제 ( http://js1jj2sk3.tistory.com/38 ) 에서 자리수가 n으로 주어지면

그런 계단수가 몇개 있는지는 O(10*N)에 구할 수 있었다.

그러면 그중에서 문제처럼 0 부터 9 까지 전부 있는 계단수는 몇개 인지 어떻게 알 수 있을까?

2. 풀이

쉬운 계단수 문제 처럼 생각해보자.

길이가 n인 계단수로 길이가 n+1인 계단수를 만들 수 있었다. n인 수의 마지막 수와 차이가 1나는 수를 뒤에 붙여주면 됐었다.

하지만 이제는 지금까지 무슨 수를 써왔는지까지 반영해야 한다.

그러면 모든 경우의 수를 무지막지하게 따지기로 하자. 계산은 컴퓨터가 해줄테니 걱정없다.

쉬운 계단수 문제처럼 DP[n][x] 배열을 만들자. n은 자리수, x는 맨 마지막 자리의 숫자이다.

하지만 이번 문제에선 지금까지 쓴 자리수를 기억해야하니,

DP[n][x][a0][a1]...[a9] 를 만들 수도 있다. a0 ~ a9 는 각기 0 ~ 9 를 썼는지에 대한 정보를 담을 것이다.

하지만 이제 계산을 어떻게 시켜야할지 코드가 매애우 어려워진다. (본인은 그럼)

그래서 차라리 DP[n][x][2 ^ 10] 짜리 배열로 만든다.

그러면

DP[10][0][1111111111(이진수)] = 10자리면서 1의 자리수는 0이며, 0 ~ 9 까지 모두 사용한 계단 수의 갯수

같은 정보를 담을 수 있다.

1111111111(2진수)가 나타내는 것은 0 ~ 9 까지 사용한 수의 상태를 0 / 1비트로 나타내고 있는 것이다.

(뒤에서 부터 0,1,2, ...)

계산을 컴퓨터에게 어떻게 맡길까?

1자리인 계단수는 9개가 있다. DP[1][X][2 ^ X] = 1 로 기저사례가 된다.

2자리인 계단수부터 점화식으로 구할 수 있다.

DP[N][X][상태비트 OR 2 ^ X] = DP[N - 1][X - 1][상태비트] + DP[N - 1][X + 1][상태비트]

상태비트를 OR 연산으로 사용한 숫자에 해당하는 비트를 세우고 넘겨주는 것이다.

따라서 가장 큰 포문 : 자리수에 해당 / 그 안에 포문 : 마지막으로 쓴 수 0 ~ 9 에 해당 / 그 안에 마지막 포문 : 가능한 모든 상태비트

로 삼중포문으로 계산할 수 있다. -> O(N * 10 * ( 2 ^ 10 )).

코드로 확인해보자.

3. 코드

10844. 쉬운 계단 수

1

9

2

17

1. 접근

인접한 모든 자리수의 차이가 1인 수를 계단 수라고 한다.

자리수가 주어질 때, 가능한 계단 수는 몇개나 되는가??

직관적인 다이나믹 프로그래밍이 가능하겠다.

작은 계단 수에서 큰 계단 수를 만들거나, 큰 계단 수에서 작은 계단 수를 만들 수도 있다.

2-1) 탑-다운 풀이

길이가 n인 계단 수는 어떤 수에서 비롯되었을까?

예를 들어 끝이 4라면, 이 계단 수는 끝이 3이거나 5인 계단 수로 만들 수 있다. (3 ->34 or 5 -> 54)

따라서

func(n,x) = 자리수가 n이고 끝이 x인 계단 수의 총 갯수 라고 정의 한다면 다음과 같다.

func(n, x) = func(n-1,x-1) + func(n-1,x+1)

끝의 예외 케이스를 정리해주면 쉽게 재귀적으로 구현 할 수 있다.

2-2) 바텀-업 풀이

길이가 n인 계단 수로 길이가 n+1인 계단 수를 몇개나 만들 수 있을까?

끝이 0이나 9가 아닌 이상 2개나 만들 수 있음은 자명하다.

그러면 이중 포문을 통해, 길이가 가장 작은 경우에서 끝 자리의 10가지 경우를 기록하고, 

이를 토대로 길이를 1늘려서 다시 확인하는 코드가 떠오를 것이다.

dp[d][x] = dp[d-1][x-1] + dp[d-1][x+1]

그게 맞당!

3-1) 코드 1

3-2) 코드 2

11049. 행렬 곱셈 순서

3
5 3
3 2
2 6

90

1. 접근

행렬 곱셈 연산의 수를 계산하는 방법이 따로 존재할 때, 임의의 행렬들이 주어질 때(순서는 고정), 어떤 행렬들 부터 곱해나가야 연산을 가장 적게하는지 묻는 문제다.

행렬들이 ABCD 로 주어진다면 다음의 곱셈 순서들이 가능하다

1) { { { A * B } * C } * D }

2) { { A * B } * { C * D } }

3) { { A * { B * C } } * D }

4) { A * { B * { C * D } } }

5) { A * { { B * C } * D } }

역시나 위의 순서들을 빠르게 만들어 낼 수 있는 패턴을 찾아내는게 포인트다. 

그러면 패턴을 구현해내고, 다이나믹 프로그래밍으로 빠르게 연산 수를 계산할 수 있겠다.

2. 풀이

패턴 : 묶음은 그보다 작은 두 묶음으로 재귀적으로 나눠진다.

2)의 경우 가장 큰 묶음은 { A * B } 와 { C * D } 로 나눠진다. 나머지 경우들은 2번씩 나눠진다.

그러면 DP 배열을 다음과 같이 정의해보자.

DP[X][Y] = 인덱스 x인 행렬부터 y까지 주어졌을 때, 우리가 원하는 정답을 보관한다.

그러면 다음과 같은 재귀함수로 배열을 갱신해 나갈 수 있다.

func(int x, int y) = DP[X][Y]를 계산하는 함수

재귀함수가 탈출하기위한 기저사례는 무엇일까?

간단히 두행렬을 곱하는 경우는 쉽게 연산 수를 계산할 수 있다.

하지만 구현을 더 간단히 하기 위해 x==y 인 경우로 탈출시키자. -> 연산하지 않는다 = return 0

이제 두 묶음으로 나눌 수 있는 경우들을 구현해야 한다.

나누는 기준은 x~y까지 가능하다. 

for (int k = x; k < y; ++k)

mm = min(mm, func(x, k) + func(k + 1, y) + m[x].r * m[k].c * m[y].c);

// m[k].c = m[k+1].r

나눠주고 계산해주는 함수들을 호출한 다음, 최소값을 기록하면 된다.

3. 코드

4. 후기

하나씩 곱해야 하는 줄 알고 삽질좀 했다.

9520. NP-hard

3
0 5 2
5 0 4
2 4 0

7

https://www.acmicpc.net/problem/9520

1. 접근

모든 도시들은 서로 연결되어 있고, 일련의 규칙으로 모든 도시를 방문해야 한다. 모든 경우 중에 최소 비용을 구해야 한다.

이 일련의 규칙이란

1) k도시를 방문하려면 k보다 작은 도시들을 전부 미리 방문했거나,

2) k를 방문한 이후 딴짓 하지 말고 k보다 작은 모든 도시들을 이후에 방문해야 한다.

따라서 도시가 1, 2 두 개라면,

[1->2] 혹은 [2->1] 이 가능하다.

도시가 3까지 있다면,

[1->2->3] 혹은 [3->1->2] 혹은 [3->2->1] 혹은 [2->1->3] 이 가능하다

[1->3->2] 순서는 3을 방문하려고 했는데, 2번 규칙에 의하면 1도시를 먼저 방문해버렸기 때문에 옳지 않은 방법이다.

[2->3->1] 순서는 2번 규칙에 의하면 2도시를 방문했으면 딴짓 하지 말고 작은 도시를 방문해야 하지만

3도시로 가버렸으므로 옳지 않은 방법이다.

이와 같은 방문순서들을 n이 주어졌을 때 만드는 패턴이 있지 않을까?

만약 그렇다면 우리는 빠르게 만들어진 순서들을 시도해보는 다이나믹 프로그래밍을 할 수 있을 텐데!

2. 풀이

패턴은 다음과 같다

먼저 1을 시퀀스에 추가한다.

그 다음 2를 시퀀스의 왼쪽이나 오른쪽에 추가한다.

그 다음 3을 시퀀스의 왼쪽이나 오른쪽에 추가한다.

...

위의 패턴으로 우리는 규칙을 만족하는 모든 방법을 만들어 낼 수 있다.

귀납적으로 증명해보자.

1) 1밖에 없는 시퀀스는 규칙을 만족한다.

2) n까지 위의 패턴으로 만든 시퀀스가 규칙을 만족한다고 가정해보자.

3) n+1 도시를 왼쪽이나 오른쪽에 추가해도 규칙을 만족한다면 우리의 패턴은 참이다.

2단계 까지 이뤄진 시퀀스의 가장 번호가 큰 도시는 당연히 n도시다.

이제 3단계에서 n+1 도시를 왼쪽에 추가한다고 하면, 우리는 규칙 2를 만족하는 방문순서를 만들어 낸것이다.

반대로 오른쪽에 추가한다고 하면, 이 시퀀스는 규칙 1을 지키는 방문순서가 될 것이다.

이제 패턴에 따라 모든 경우를 계산해 줄 함수를 정의해보자.

func(현재 시퀀스의 왼쪽 도시 번호, 현재 시퀀스의 오른쪽 도시 번호, 추가할 도시 번호)

= 현재 상황에서의 만들 수 있는 종래의 최소비용 = func(int x, int y, int num)

기저사례는 num이 n+1까지 확장될 경우다. 더 이상 추가할 도시가 없다.

이 도시 num을 왼쪽에 추가한다면, 시퀀스의 왼쪽은 num이 될 것이므로,

func(num, y, num+1) + dist[x][num] 

이 도시 num을 오른쪽에 추가한다면, 시퀀스의 오른쪽은 num이 될 것이므로,

func(x, num, num+1) + dist[y][num]

두 경우를 계산해보고, 둘 중 작은 값이 정답이다. 메모이제이션으로 O(n*n).

3. 코드

4. 후기

패턴을 못찾았다면 난리 필 문제

10835. 카드게임

3
3 2 5
2 4 1

7

https://www.acmicpc.net/problem/10835

1. 접근

규칙에 따라 게임을 해야 할 때, 얻을 수 있는 최대의 점수를 구해야 한다.

어쩌면 처음의 카드 배열을 보고 최대 점수를 얻는 전략이 있을 수도 있다.

하지만 빡대가리로서는 짐작도 안가므로, 모든 경우를 계산해보기로 하자.

또한 다이나믹 프로그래밍으로 시간을 절약해 보기로 하자.

2. 풀이

자연스럽게 재귀적인 풀이가 떠오른다.

func(왼쪽 더미의 남은 카드 수, 오른쪽 더미의 남은 카드 수) = 이런 상황에서 얻을 수 있는 최대의 점수

= func(int x, int y)

라는 함수로 모든 계산을 맡겨 보기로 한다.

현재 상황에서 일단 내릴 수 있는 선택은 총 세가지다.

1) 왼쪽을 버린다 (+0점) -> func(x-1, y)

2) 왼쪽, 오른쪽 둘 다 버린다 (+0) func(x-1, y-1)

3) 왼쪽 카드 점수(a점) < 오른쪽 카드 점수(b점) 이라면 오른쪽을 버린다 (+b점) -> func(x,y-1) + b

따라서 함수내에 재귀적으로 세가지 함수를 호출해주면 된다.

기저사례는 양쪽 카드 더미 중 한쪽이라도 바닥나는 경우다. 

3. 코드

4. 후기

응^^ 중등부

3032. 승리

3
3 1 5

3

1. 접근

두 게이머가 게임을 한다.

다만 두 명 모두 최선의 전략을 구사할 줄 알고(근데 우리는 모른다) 게임에 임할 때,

첫 순서인 플레이어가 이길 수 있는 경우의 수를 묻는 문제다.

역시나 짱구를 굴려봐도 최선의 전략이 뭔지 모르겠으니까, 모든 경우를 시도해보는(하지만 빠른) 다이나믹 프로그램을 써보자.

고려할 점은 n개의 수가 일렬로 있는게 아니라 원형 배열에 있다는 점이다.

2. 풀이

처음의 선택으로 원형배열은 일렬의 배열로 바뀐다. 선택의 양쪽 수가 배열의 양쪽 끝 수가 될 것이다.

그러면 카드게임 : http://js1jj2sk3.tistory.com/33 의 경우와 같아진다.

이기기 위한 전략이 뭔지는 모르겠지만, 나의 점수를 최대한으로 하려는 것이다. (상대의 점수를 최소한으로 하려는 것이다)

다만 문제가 요구하는 것은 첫 번째 선택으로 올바른 경우를 세야 하므로 지금까지의 turn을 고려하는 함수는 만들기 어렵다.

(내 머리로 못함)

func(int x, int y) = 남은 배열(입력받은 배열)이 x부터 y일때, 낼 수 있는 최대한의 점수차이.

위와 같이 정의한다면 현재 순서가 누구인지 고려할 필요가 없다.

기저사례는 x==y인 경우로, 입력의 x번째 수가 홀수라면 1, 아니면 0을 리턴해주자.

이제 왼쪽을 고르거나 오른쪽을 고르는 경우를 모두 계산해주면 된다!

한 쪽을 고를 때 만들 수 있는 최대한의 점수차이는 어떻게 기술해야 할까?

한 쪽을 고르고 얻은 점수 - 나머지로 만드는 최대한의 점수 차이 = 한 쪽을 고르면 얻는 최대한의 점수차이

int left = func(x, x) - func((x + 1) % n, y);

int right = func(y, y) - func(x, (y + n - 1) % n);

라고 쓸 수 있다.

이걸 이해하는게 개인적으로 엄청 힘들었다 (멍청). 이번엔 턴을 고려하지 않는다.

내 턴이라 생각해보면, 선택 이후 턴이 넘어가기 때문에, 당연히 상대방은 최선의 전략을 구사하므로 함수를 호출하신다.

상대가 만드는 점수차는 당연히 내 점수에서 까야 된다.

왼쪽을 선택해서 만드는 점수차는 1점 - 3점차 = -2점차가 된다.

func(i, i) - func((i + 1) % n, (i + n - 1) % n) > 0

이라면 내가 이긴다.

3. 코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[101][101];
int n, t, i;
int func(int x, int y) {
	if (x == y) 
		return dp[x][y];
		
	if (dp[x][y] != -1)
		return dp[x][y];
	int left = func(x, x) - func((x + 1) % n, y);
	int right = func(y, y) - func(x, (y + n - 1) % n);
	return dp[x][y] = max(left, right);
}
int main() {
	scanf("%d", &n);
	memset(dp, -1, sizeof(dp));
	for (i = 0; i < n; ++i) {
		scanf("%d", &dp[i][i]);
		dp[i][i] %= 2;
	}
	
	int ans = 0;
	for (i = 0; i < n; ++i)
		if (func(i, i) > func((i + 1) % n, (i + n - 1) % n))
			ans++;
	printf("%d", ans);
	return 0;
}

11062. 카드 게임

2
4
1 2 5 2
9
1 1 1 1 2 2 2 2 2

6
8

1. 접근

두 명이 일련의 규칙에 따라 게임을 진행한다.

단 둘다 최선의 전략을 알고 있다 가정할 때(최선의 전략이 뭔지는 아직 모른다),

선 턴인 주인공이 최대로 얻을 수 있는 점수는 몇 점일까?

계속되는 알고리즘 게임의 일종으로, 아무리 짱구를 굴려봐도 최선의 전략이 무엇일지는 감이 안오므로,

모든 경우를 계산해보는(하지만 빠른) 다이나믹 프로그래밍으로 풀어보자.

2. 풀이

dp[turn][남은 카드들 중 왼쪽 끝][남은 카드들 중 오른쪽 끝]으로 배열을 잡아보자.

턴은 번갈아 진행되며, 남은 카드들의 양 쪽 끝은 0 ~ n-1 까지다.

다이나믹 프로그래밍으로 한 번 기록된 dp배열에 접근하면 상수시간에 리턴되므로 배열 크기에 비례한 O(2*n*n)에 풀 수 있겠다.

이제 문제를 풀어줄 함수를 정의해보자.

func(int turn, int x, int y) = 턴이 turn이고, 왼쪽 끝은 x, 오른쪽 끝은 y 일 때 내가 얻을 수 있는 최대의 점수.

우리는 이제 기저사례로 x==y인 경우를 생각해 볼 수 있다.

남은 카드가 한 장이란 말로, 내 턴이였다면 점수를 취하고, 상대 턴이라면 "그냥 그랬구나" 하고 넘어가면 된다.

이제 왼쪽을 가져가든지, 오른쪽을 가져가든지 점수가 얼마나 될지 계산해봐야 한다.

내 턴이였다면 실제로 점수 계산을 위한 코드가 있어야 할테고,

상대 턴이였다면, 상대도 최선의 전략으로 플레이하기 때문에 양 쪽 플레이 중 나의 점수를 최소로 하는 플레이를 할 것이다.

3. 코드