[알고리즘 문제풀이] 기타 코딩테스트 1-5

 

문제 : 

두더지 게임
A씨는 두더지 게임을 좋아한다. 두더지 게임판은 가로 세로의 크기가 1로 이뤄진 작은 칸들이 모여 가로와 세로의 크기가 N인 N x N 의 크기로 이루어져있고 총 N^2마리의 두더지가 있다. 이 두더지들은 특정 시간에 올라와서 1초 동안 올라와 있는다. 이때 A씨는 1초에 1번만 두더지를 칠 수 있고 A씨가 두더지를 망치로 치게 되면 해당 두더지에 적혀있는  점수를 얻게 되며 망치로 치지 않으면 1초 후에 두더지는 다시 들어간다. 예를 들어, 판의 크기가 2 x 2이고, 아래와 같이 두더지가 올라온다고 하자.

두더지 1 : 1초, 3초, 5초 – 점수 1
두더지 2 : 2초, 4초 – 점수 2
두더지 3 : 1초, 2초 – 점수 3
두더지 4 : 3초 – 점수 4

위와 같이 두더지 1에는 점수 1점이, 두더지 2에는 점수 2점, 두더지 3에는 점수 3점, 그리고 두더지 4에는 점수 4점이 적혀있다고 하자. 그렇다면 아래와 같은 상황을 생각할 수 있다.
(t는 두더지 게임을 시작한 뒤 흐른 시간을 의미하여 X 표시는 두더지가 올라온 것을 의미한다.)

시간별로 위의 그림과 같이 두더지가 올라와 있는 것을 알 수 있다. 이 상황에서 A씨가 점수를 가장 많이 얻기 위해서는 아래 그림과 같이 두더지를 망치로 쳐야 한다.

이렇게 되면 A씨가 얻게 되는 점수는 3 + 3 + 4 + 2 + 1 = 13점이 되고, 이것이 A씨가 게임을 통해 얻을 수 있는 최대 점수이다.

N x N 크기의 게임판에 존재하는 N^2마리의 두더지 각각에 대해서 올라오는 시간이 주어질 때, A씨가 게임을 통해 얻을 수 있는 점수의 최댓값을 출력하시오.

 

 

 

입력 : 

첫 번째 줄에 게임판의 크기 정수 N을 입력받는다.
1 ≦ N ≦ 5
이후 N^2 개의 줄에 대해서 각각의 두더지에 대한 정보를 입력 받는다. i번째 줄은 공백을 구분자로 
S K t1 t2 ... 로 입력받으며, S는 i 번째 두더지의 점수, K는 두더지가 올라오는 횟수, 
그리고 이후 t1 t2 ... 은 두더지가 올라오는 시간이다. 두더지가 올라오는 시간은 오름차순으로 입력되며, 중복되지 않는다.
1 ≦ K ≦ 100
t ≦ 100,000,000

 

ex)

2
1 3 1 3 5
2 2 2 4
3 2 1 2
4 1 3

 

 

출력 : 

A씨가 게임을 통해 얻을 수 있는 점수의 최댓값을 출력한다.

 

ex)

13

 

 

 

풀이 : 

#include <iostream>
#include <map>

using namespace std;
map<int, int>m;

int N; //5이하
int S; //점수
int K;
int t;
int hap = 0;

int main() {
	cin >> N;
	for (int i = 0; i < N * N; i++) { //N^2 만큼 수행
		cin >> S >> K;
		for (int j = 0; j < K; j++) { //두더지가 K번 올라온다
			cin >> t;
			if (m[t] <= S) {
				int re = m[t];
				m[t] = S; //큰값으로 갱신한다.
				hap = hap - re + S;
			}
		}
	}
	cout << hap << endl;
	return 0;
}

 

참고자료 : map container

dbstndi6316.tistory.com/29

[개념정리] map container

추가적으로 여기선 map을 사용했지만.. unordered map 을 사용할 수도 있을것이다.