CodeDrive

문제:

근우는 오늘 재미있는 카드 게임을 배우고 있다. 카드는 빨간색, 파란색, 노란색, 녹색의 네 가지 색이 있고, 색깔별로 1부터 9까지 숫자가 쓰여진 카드가 9장씩 있다. 카드는 모두 36(=4x9)장이다. 근우가 배운 카드 게임은 36장의 카드에서 5장을 뽑고, 아래와 같은 규칙으로 정수를 계산하는 것이다.

각 카드는 다음과 같이 나타낸다. 카드의 색깔은 영어 대문자 R, B, Y, G로 나타내는데, R은 빨간색, B는 파란색, Y는 노란색, G는 녹색을 뜻한다. 예를 들어서 Y8은 노란색 8을 나타내고, B5는 파란색 5를 나타낸다.

<점수를 정하는 규칙>

1. 카드 5장이 모두 같은 색이면서 숫자가 연속적일 때, 점수는 가장 높은 숫자에 900을 더한다. 예를 들어, 카드가 Y4, Y3, Y2, Y5, Y6 일 때 점수는 906(=6+900)점이다.
2. 카드 5장 중 4장의 숫자가 같을 때 점수는 같은 숫자에 800을 더한다. 예를 들어, 카드가 B3, R3, B7, Y3, G3 일 때 점수는 803(=3+800)점이다.
3. 카드 5장 중 3장의 숫자가 같고 나머지 2장도 숫자가 같을 때 점수는 3장이 같은 숫자에 10을 곱하고 2장이 같은 숫자를 더한 다음 700을 더한다. 예를 들어, 카드가 R5, Y5, G7, B5, Y7 일 때 점수는 757(=5x10+7+700)점이다.
4. 5장의 카드 색깔이 모두 같을 때 점수는 가장 높은 숫자에 600을 더한다. 예를 들어, 카드가 Y3, Y4, Y8, Y6, Y7 일 때 점수는 608(=8+600)점이다.
5. 카드 5장의 숫자가 연속적일 때 점수는 가장 높은 숫자에 500을 더한다. 예를 들어 R7, R8, G9, Y6, B5 일 때 점수는 509(=9+500)점이다.
6. 카드 5장 중 3장의 숫자가 같을 때 점수는 같은 숫자에 400을 더한다. 예를 들어 R7, Y7, R2, G7, R5 일 때 점수는 407(=7+400)점이다.
7. 카드 5장 중 2장의 숫자가 같고 또 다른 2장의 숫자가 같을 때 점수는 같은 숫자 중 큰 숫자에 10을 곱하고 같은 숫자 중 작은 숫자를 더한 다음 300을 더한다. 예를 들어, R5, Y5, Y4, G9, B4 일 때 점수는 354(=5X10+4+300)점이다.
8. 카드 5장 중 2장의 숫자가 같을 때 점수는 같은 숫자에 200을 더한다. 예를 들어, R5, Y2, B5, B3, G4 일 때 점수는 205(=5+200)점이다.
9. 위의 어떤 경우에도 해당하지 않을 때 점수는 가장 큰 숫자에 100을 더한다. 예를 들어, R1, R2, B4, B8, Y5 일 때 점수는 108(=8+100)점이다.

입력으로 카드 5장이 주어질 때, 카드 게임의 점수를 구하는 프로그램을 작성하시오. 두 가지 이상의 규칙을 적용할 수 있는 경우에는 가장 높은 점수가 카드 게임의 점수이다.

입력:

첫째 줄부터 다섯째 줄까지 한 줄에 카드 하나씩 입력된다. 카드의 색깔과 숫자 사이에는 빈 칸이 하나 있다.

출력:

한 줄에 카드의 점수를 출력한다.

풀이방법:

 주어진 규칙에 알맞게 점수계산을 하면 된다. 규칙 조건에 따라 중복으로 계산이 되는 경우가 존재하는데 조건문을 통해 최댓값을 가지도록 한다.

규칙을 크게 보면 다음과 같이 세 가지가 있다.

<색 조건>

1. 모두 같은 색을 가지는 가?

<숫자 조건>

2. 숫자가 연속 되는가?

3. 공통된 숫자가 K개 있다.

따라서 각 조건에 대해 다음과 같은 방법을 사용한다.

1. set 연산을 사용해 원소의 갯수가 1이면 모두 같은 색이다.

2. 가장 큰 값과 가장 작은 값의 차이가 4면 연속되어 있다.

3. 숫자가 key, 갯수가 value은 dict 자료형을 사용한다.

위 방법들 사용해서 해당하는 규칙을 찾고 그에 맞게 계산하면 된다.

문제링크:

www.acmicpc.net/problem/2621

문제:

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

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

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