[백준 1766 - 골드 2] 문제집.cpp

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

1766번: 문제집

처음엔 시간 초과.

진짜 무식한 방법이긴 했다.

문제 풀이 여부를 나타내는 solved 배열을 체크하면서,

풀었으면 다음 문제로 넘어간다.

그리고 해당 문제의 조건의 사이즈가 0이면,

문제를 푼 것으로 하고, 다른 문제들의 풀이 조건 중에

방금 푼 문제가 있으면 그 문제를 없애주었다.

이러니 시간 초과가....

 

친구들과 함께 알고리즘 스터디를 하고 있는데,

다른 친구는 우선순위 큐를 이용하여 문제를 풀었다.

하지만, 나는 우선순위 큐의 존재조차 몰라서.. 이상한 방법으로나마 풀긴 했다.

 

가장 큰 차이는 solved 배열이었다.

첫 풀이에서는 단순하게 0, 1을 저장하는 배열이었지만,

이번엔 n번째 문제를 풀기 위해 먼저 풀어야하는 문제의 수를 기록해주었다.

 

먼저 풀어야하는 문제가 있으면 -1을 해주었다.

따라서, solved[n]이 -5면 5문제를 먼저 풀어야하는 문제.

solved[n]이 0이면 현재 바로 풀 수 있는 문제.

 

그리고 map을 이용해서

이 문제를 풀면, 다음은 어떤 문제를 풀 수 있는지를 저장해주었다.

마찬가지로 N개를 풀 때까지 while 문.

첫 번째 문제부터 체크하며, solved가 0인 경우에만 추가적인 작업을 해준다.

 

문제를 풀고, 문제 풀이 수를 증가시켜주었고,

어떤 문제가 풀렸으니, 이로 인해 먼저 풀어야될 문제의 수가 하나 줄었기 때문에

map에 저장한 정보를 이용해 solved값을 증가시켜주었다.

이를 반복해서 성공.