CodeDrive

문제:

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.

각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.

주어진 필드가 위의 그림과 같고, 예은이의 수색범위가 4라고 하자. ( 원 밖의 숫자는 지역 번호, 안의 숫자는 아이템 수, 선 위의 숫자는 거리를 의미한다) 예은이가 2번 지역에 떨어지게 되면 1번,2번(자기 지역), 3번, 5번 지역에 도달할 수 있다. (4번 지역의 경우 가는 거리가 3 + 5 = 8 > 4(수색범위) 이므로 4번 지역의 아이템을 얻을 수 없다.) 이렇게 되면 예은이는 23개의 아이템을 얻을 수 있고, 이는 위의 필드에서 예은이가 얻을 수 있는 아이템의 최대 개수이다.

입력:

첫째 줄에는 지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)이 주어진다.

둘째 줄에는 n개의 숫자가 차례대로  각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)를 알려준다.

세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.

출력:

예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

풀이방법:

플로이드-와샬 알고리즘을 적용해서 이 문제를 풀 수 있다. 플로이드-와샬 알고리즘은 주어진 그래프의 경로로 가중치를 초기화한 후 i에서 j로 가는 경로에 k가 추가 되었을 때, 이전의 경로의 가중치보다 작아지는지 확인하면 된다. 

플로이드-와샬로 초기화를 완료한 뒤에, 지역의 개수 n을 반복문으로 순회한다. 순회하면서 임계점에 해당하는 값인 m보다 작은 값들을 모두 더해주고, 마지막에 현재 시작한 지역의 값을 더해주도록 한다. 이 중 가장 큰 값을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/14938

문제:

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력:

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

출력:

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

풀이방법:

 이러한 문제는 최소 스패닝 트리를 사용해서 푸는 전형적인 문제다. Kruskal, Prim 알고리즘으로 풀 수 있으며, 이번 문제는 Prim 알고리즘을 활용해서 풀었다.

 Prim 알고리즘은 다음의 순서대로 작동한다.

1. 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다.
2. 그래프의 모든 변이 들어 있는 집합을 만든다.
3. 모든 꼭짓점이 트리에 포함되어 있지 않은 동안
   1. 트리의 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다.

 이 알고리즘이 종료되었을 때 만들어진 트리는 최소 비용 신장 트리가 된다. [출처: Prim 알고리즘 위키피디아]

따라서 위 알고리즘대로 해당 노드로 이동하는 최소 비용을 의미하는 distance 배열을 INF로, 전체 가중치를 가지고 있는 vertice를 초기화 하고, 모든 컴퓨터를 방문했는지 확인할 수 있는 visited 배열을 만든다.

 이제 1번 컴퓨터(인덱스상 0번)를 임의로 선택하여 위 알고리즘대로 트리를 만들기 시작한다. 1번 컴퓨터로 향하는 distance는 0이다. (문제 조건 상 a와 b가 같을 수 있다고 하는데 큰 의미는 없는 것 같다.) distance와 visited 배열을 바탕으로 선택해야 하는 distance를 고른다.( 첫번쨰의 경우에는 당연히 1번 컴퓨터만 distance가 변경되었으므로 1번 컴퓨터다.) 1번 컴퓨터가 선택되었으므로, 이 컴퓨터와 연결 된 Edge들을 distance에 반영한다.

 위 과정을 모든 컴퓨터를 다 방문할 때까지 반복하며, 알고리즘이 종료되었을 때의 distance의 합이 최소 비용을 의미하게 된다.

문제링크:

www.acmicpc.net/problem/1922

문제:

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

입력:

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력:

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

풀이방법:

**python3이 아닌 pypy3으로 통과한 문제입니다.**

플로이드-와샬 알고리즘을 적용하면 쉽게 풀 수 있는 문제다. 플로이드-와샬 알고리즘은 주어진 그래프의 경로로 가중치를 초기화한 후 i에서 j로 가는 경로에 k가 추가 되었을 때, 이전의 경로의 가중치보다 작아지는지 확인하면 된다. 

이 과정을 마친 후에 a to b가 inf가 아니면 -1을, b to a가 inf가 아니면 1을 inf면 0을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/1613

문제:

웅찬이는 근성이 대단한 도둑이다. 그래서 금고를 털 때, 모든 조합을 눌러본다. 예를 들어 비밀번호가 3글자 라는 사실을 알 때, 000, 001, 002, 003, … 998, 999의 모든 조합을 눌러본다. 그러나 웅찬이는 선견지명이 있어서 비밀번호에 어떤 숫자가 들어가는지 일부 알 수 있다. 예를 들어 3글자 비밀번호에 0이 들어감을 안다면 999 와 같이 0이 들어가지 않는 수는 가능성이 없다. 그러나 000, 012, 030과 같은 수는 가능하다. 비밀번호의 길이와 선견지명으로 알게된 비밀번호의 일부 숫자가 주어질 때, 모든 가능한 비밀번호의 개수를 출력하는 프로그램을 작성하시오.

입력:

첫줄에 비밀번호의 길이 n (1 ≤ n ≤ 7), 선견지명으로 알게된 비밀번호에 들어가는 수 m(0 ≤ m ≤ n) 이 주어지고, 둘째 줄에 m개의 서로 다른 숫자(0~9)가 주어진다.

출력:

가능한 모든 비밀번호의 개수를 출력한다.

풀이방법:

 처음에는 dfs를 활용한 백트래킹 방법으로 풀었다가 시간초과가 발생했다. 다른 방법을 생각해보던 중 수학적으로 풀 수 있음을 알게 되었다.

 따라서 포함배제의 원리를 사용해서 이 문제를 푼다. 문제에서 주어지는 n과 m만을 사용해서 풀수 있다.

m개의 수를 반드시 포함하는 경우의 수를 구하기 위해서 전체 가능한 경우의 수에서 m개의 수를 포함하지 않는 경우의 수를 빼는 것으로 구한다. 즉 다음과 같다.

비밀번호에 들어가는 수 m을 반드시 포함하는 비밀번호의 수 = 전체 비밀번호의 수 - m개의 수가 포함되지 않은 비밀번호의 수

전체 경우의 수는 10^n가 된다. m개의 수가 포함되지 않은 비밀번호의 수는 포함배제의 원리를 사용해서 구하도록 한다. 즉 구하는 식은 다음과 같이 된다.

answer = 10^n - mC1*9^n+mC2*8^n-mC3*7^n+.....

문제링크:

www.acmicpc.net/problem/13908

문제:

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다. 

입력:

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력:

check 연산이 주어질때마다, 결과를 출력한다.

풀이방법:

python의 set의 내장함수를 적절히 사용하면 쉽게 풀 수 있다.

1. add : set의 add를 사용한다. python의 set은 중복을 지원하지 않기 때문에 x가 이미 있는 경우에는 중복으로 들어가지 않는다.

2. remove : set에서 원소를 제거하는 방법은 remove와 discard가 있다. remove는 원소가 없는 경우 에러를 반환하지만 discard를 그렇지 않다. 따라서 discard를 사용한다.

3. check : python의 in 기능을 사용한다.

4. toggle : 1. add, 2. remove, 3.check의 기능을 적절히 활용하면 된다. 이 명령어에서 원소를 제거하는 경우에는 항상 있다는 보장이 있으므로 remove를 사용했다.

5. all : S를 재정의한다.

6. empty: S를 재정의한다.

연산의 수가 매우 많으므로 sys.stdin.readline()를 사용해서 빠른 입력을 사용한다.

문제링크:

www.acmicpc.net/problem/11723

문제:

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.

A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 자연수 중에 금민수인 것의 개수를 출력한다.

풀이방법:

 주어진 수가 1,000,000,000로 엄청 크게 주어졌기 때문에 A~B 사이의 수가 4와 7로 이루어져있는지 탐색하는 것은 시간초과가 발생할 것이다. 따라서4와 7로 구성된 숫자를 만들면서 이 숫자가 A~B 사이에 있는지 확인하도록 한다.

 A와 B가 큰 수로 주어질 수도 있기 때문에 깊이라는 개념을 사용해서 최대한 탐색할 수 있도록 했다. 깊이는 상한값으로 인해 최대 9까지 가능하다. 깊이라는 개념이 추가되었기 때문에 깊이우선탐색을 사용해서 값을 만들어내도록 한다.

 생성된 값이 주어진 범위 안에 들어 있으면 count를 1 올려주고 상한 값을 넘어가면 더 빠른 탐색을 위해서 0을 반환하도록 했다. 하한값에 보다 작은 값에 대해서는 조건이 없는데, 그 이유는 앞서 말했던 A와 B가 큰 수로 주어졌을 때, 그 범위 내까지는 이동하도록 하기 위함이다.

문제링크:

www.acmicpc.net/problem/1527

문제:

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 2^28이다.

출력:

합이 0이 되는 쌍의 개수를 출력한다

풀이방법:

***Pypy3으로 통과한 문제입니다.***

 이 문제를 그냥 완전탐색으로 풀면 O(N^4)가 되고, N은 최대 4000까지 주어지므로 시간초과가 발생할 것이다. 따라서 4개의 배열을 두개씩 묶어서 O(N^2)으로 줄이도록 한다.

 A와 B의 가능한 합의 경우의 수를 담고 있는 one을 해싱 방법으로 딕셔너리 형태로 저장한다. 포함되는 정수가 중복이 없다는 조건이 없기 때문에, 해당하는 키가 여러개 존재할 수 있으므로 key,value = (두 정수의 합, 나타나는 횟수)와 같이 딕셔너리 형태로 저장한다.

 C와 D의 가능한 합의 경우의 수를 구하면서 이 합의 마이너스 부호를 취한 것이 one 딕셔너리에 있다면 합이 0이 되는 경우이므로 value 값을 answer에 더하도록 한다.

**[21.01.17 수정]현재 재채점으로 인해 아래 코드도 통과하지 못합니다.**

문제링크:

www.acmicpc.net/problem/7453

문제:

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력:

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력:

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이방법:

www.acmicpc.net/problem/2293 의 동전 1 문제를 응용해서 풀면 된다. 이 문제에서는 k원을 만드는 경우의 수를 구하는 문제였지만, 이 문제에서는 최솟값을 구해야 한다. 따라서 동전의 가치가 최대 100,000원이므로 초기값으로 100,001원(0원은 0으로 초기화 한다.) 으로 설정하고, 작은 동전부터 사용해서 각 p원을 만들 수 있는 최소 갯수를 구하도록 한다.

 이 문제의 예시로 생각하면 다음과 같다. (1,5,12)원이 있을 때, 1원으로 15원을 만드는 방법은 다음과 같이 비교할 것이다.

 위 표는 다음 두 조건을 비교하면서 채워나갔다. 1원을 만드는 경우로 예시를 든다.

1. 현재 값을 그대로 사용한다. dp[1]

2. 0원에서 1원을 더해서 사용한다. dp[1-1]+1

3. 1과 2중 더 작은 값을 사용한다. min(dp[1],dp[1-1]+1)

즉 이를 일반화 하면 다음과 같다. min(dp[n],dp[n-c]+1), n은 현재 만들고자 하는 금액, c는 현재 사용하고 있는 동전의 가치다.

 5원을 사용하는 경우는 1~4원은 만드는 것이 불가능하므로 5원부터 반복한다.

 12원을 사용하는 경우는 1~11원은 만드는 것이 불가능하므로 12부터 반복한다.

 최종적으로는 dp[k]원이 초기화한 값에서 변경이 되었다면 dp[k]를 출력하고, 바뀌지 않았다면 -1을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/2294

문제:

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력:

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력:

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

풀이방법:

0으로 초기화 된 DP 배열을 미로의 값에 따라 초기화 하면서 진행하면 된다.

이 문제의 예제를 통해서 설명한다. 처음에는 다음과 같이 초기화 된다.

numbers[0]의 값은 1이므로 dp[1]의 값을 업데이트한다.

numbers[1]의 값은 2이므로 dp[2]~dp[3]의 값을 업데이트한다.

numbers[2]의 값은 0이므로 넘어가고, numbers[5]까지 반복하면 아래와 같이 된다.

 만약 이미 dp[i+j]에 0이 아닌 다른 값이 초기화되어 있다면, dp[i+j]값과 dp[i]+1값 중 작은 값을 사용하도록 한다. 끝까지 진행하면 다음과 같이 된다.

 위 작업을 모두 반복했을 때, 맨 마지막 값이 0이 아닌 다른 값으로 바뀌었다면, 끝에 도달할 수 있는 것이므로 해당 값을 출력하면 되고, 아니라면 -1을 출력하도록 한다. 그리고 생각해야 하는 예외가 두가지가 있다.

 첫번째는 5 (0,0,0,1,0)과 같은 경우가 있다. 이런 경우는 if dp[i]==0 and i!=0 와 같은 조건문을 넣어서 해결해준다. 정상적으로 진행될 때, dp에 0 값은 dp[0]을 제외하고 생기면 안되기 때문이다.

 두번째는 1 (0) 이다. 이 경우에는 시작과 동시에 오른쪽 끝으로 도달한 경우이기 때문에, 마지막 출력하는 단계에서 예외처리로 0을 출력하도록 한다.

문제:

지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다.

이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다. 

다음 예는 세 장 씩 두 더미의 카드를 가지고 게임을 시작하는 경우이다.

이 경우, 우선 오른쪽 카드 2가 왼쪽 카드 3보다 작으므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 모두 버리거나, 규칙 (2)에 따라 오른쪽 카드만 버릴 수 있다. 만약 오른쪽 카드만 버리는 것으로 선택하면, 2만큼 점수를 얻고 오른쪽 카드 2는 버린다. 이제 오른쪽 더미의 제일 위 카드는 4이고 이는 왼쪽 카드 3보다 크므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수 있다. 만약 둘 다 버리는 것으로 선택하면, 이제 왼쪽 카드는 2가 되고 오른쪽 카드는 1이 된다. 이 경우 다시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 왼쪽 카드만 버리는 것으로 선택하면 이제 왼쪽 카드는 5가 되고 오른쪽 카드는 1이 된다. 이 경우에도 역시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 오른쪽 카드만 버리는 것으로 선택하면 1만큼 점수를 얻고 오른쪽 카드 1은 버린다. 이제 오른쪽 더미에는 남은 카드가 없으므로 규칙 (3)에 따라 게임이 끝나며 최종 점수는 2+1=3이 된다.

두 더미의 카드가 주어졌을 때, 게임을 통해 얻을 수 있는 최종 점수의 최댓값을 출력하는 프로그램을 작성하시오. 위 예에서 최종 점수의 최댓값은 7이다.

입력:

첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오른쪽 더미의 카드에 적힌 정수 B(1 ≤ B ≤ 2,000)가 카드 순서대로 N개 주어진다. 각 더미에는 같은 숫자를 가진 카드가 두 개 이상 있을 수 있다.

출력:

얻을 수 있는 최종 점수의 최댓값을 출력한다.

풀이방법:

 DP를 사용해서 풀어야 하는 문제다. 처음에는 재귀로 이 문제를 접근했었는데, 시간초과랑 메모리 초과가 반복적으로 발생해서 반복문을 사용해서 풀게 되었다. 반복문을 사용해서 풀게 될 경우에는 정방향으로 DP를 배치하는 것이 아닌, 역방향으로 DP를 구성해야 한다고 한다. 마치 재귀로 풀이 되던 것들이 반복문으로 풀어져서 풀이 된다고 생각하면 된다.

문제링크:

www.acmicpc.net/problem/10835