BOJ 18866 : 젊은 날의 생이여

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

18866번: 젊은 날의 생이여

한 2달전쯤에 틀렸던 문제인데, 주말에 심심해서 풀어봤다.

 

문제에서 주어진 조건은 다음과 같다.

 

• N개의 날 중, 1~ K까지는 젊은 날, K+1~N까지는 늙은 날이다.
  
  • 임의의 젊은 날의 행복도는 임의의 늙은 날의 행복도보다 높다.
  • 임의의 젊은 날의 피로도는 임의의 늙은 날의 피로도보다 낮다.
• 가끔 행복도, 피로도에 누락된 값이 있는데, 이는 0으로 표현된다.
• 이때 가능한 최대 젊은 날을 만족하는 수 K를 구하라

 

조건을 풀어서 써보면,

 

• 젊은 날의 최소 행복도는 늙은 날의 최대 행복도보다 높다.
• 젋은 날의 최대 피로도는 늙은 날의 최소 피로도보다 높다.

따라서, 젊은 날의 경우는 1~N까지 돌면서 최소 행복도, 최대 피로도를 젊은 날 배열에 저장하고,

늙은 날의 경우는 N~1까지 (거꾸로) 돌면서 최대 행복도, 최소 피로도를 늙은 날 배열에 저장한다.

(이때 0의 경우는 일단 최대,최소 갱신에 사용하지 않는다.)

 

그리고 (K-1)~1 까지 돌면서 젊은 날로 지정하고, (당연히 그 뒤에 칸부터는 늙은 날) 위의 조건을 만족하는지 판별한다.

다시 말해, 뒤에서부터 모든 K에 대해 판별한다.

정확히 말하자면, K번째 칸이 젊은 날일때,

 

• 1~K까지의 최소 행복도 < K+1~N까지의 최대 행복도
• 1~K까지의 최대 피로도 < K+1~N까지의 최소 피로도

이 두가지 조건을 만족하면 된다는 것이다. 앞서 배열들을 돌면서 값을 기록해 뒀으니 비교는 쉽게 할 수 있다.

그리고 0의 경우 헷갈릴 수 있는데, 0은 아무 값이나 대입될 수 있다는 것을 떠올려 보면 된다.

 

시간 복잡도에 대해서는 딱히 문제될 것이 없다. 모두 O(N) 이다.

 

소스코드는 깃허브에 올려두었다.

https://github.com/onaeonae1/ProblemSovling/blob/master/BOJ%2018866.cpp

onaeonae1/ProblemSovling

 

*백준에는 부분합이라고 분류되어 있는데, 부분합을 딱히 쓰지는 않는다. 어떤 알고리즘으로 분류해야 할 지 모르겠다.