[백준/파이썬][Gold IV] 젊은 날의 생이여 - 18866

[Gold IV] 젊은 날의 생이여 - 18866

문제 링크

성능 요약

메모리: 254332 KB, 시간: 840 ms

분류

누적 합

제출 일자

2025년 2월 11일 23:41:46

문제 설명

욱제는 입대를 앞두고 <이등병의 편지>를 부르고 있다.

… 이제 다시 시작이다 젊은 날의 생이여 …

그런데 과연 욱제에게 젊은 날이 있었을까? 욱제에게 젊은 날이 있었는지 알아보자.

먼저, N년간 욱제의 행복도와 피로도가 주어진다. 행복도와 피로도는 양의 실수 값을 가진다. 어떤 1 ≤ K < N에 대해 1, 2, …, K년은 욱제의 젊은 날이고, K + 1, K + 2, …, N년은 욱제의 늙은 날이다.

젊은 날과 늙은 날은 다음의 조건을 만족한다:

• 임의의 젊은 날의 행복도는 임의의 늙은 날의 행복도보다 높다.
• 임의의 젊은 날의 피로도는 임의의 늙은 날의 피로도보다 낮다.

욱제는 자신의 행복도와 피로도를 이용하여 자신의 젊은 날을 알아보려 한다. 하지만, 일부 값이 누락되었다. 욱제를 도와주자.

입력

첫째 줄에 N이 주어진다.

둘째 줄부터 N개의 줄에는 두 정수 u_i, v_i (1 ≤ i ≤ N)가 주어진다. u_i, v_i가 1 이상일 경우 각각 i년의 행복도와 피로도를 나타내며, 0인 경우에는 값이 누락되었음을 의미한다.

출력

욱제의 젊은 날이 될 수 있는 최대 기간, 즉 문제의 조건을 만족할 수 있는 최대의 1 ≤ K < N을 출력한다. 단, 이러한 K가 없을 경우, -1을 출력한다.

풀이

INF = 1 << 32

def main() :
    N = int(input())
    days = [(0, 0)] # 1-based indexing을 위한 더미 데이터

    max_happy = -1
    min_happy = INF
    max_fatigue = -1
    min_fatigue = INF

    # 각 날짜별 행복도와 피로도 입력
    for _ in range(N) :
        u, v = map(int, input().split())
        days.append((u, v))

    # youth 배열 계산 (앞에서부터)
    youth = [(0, 0)]
    for i in range(1, N + 1) :
        if days[i][0] != 0 and days[i][0] < min_happy :
            min_happy = days[i][0]
        if days[i][1] != 0 and days[i][1] > max_fatigue :
            max_fatigue = days[i][1]
        youth.append((min_happy, max_fatigue))

    # old 배열 계산 (뒤에서부터)
    old = [(0, 0)] * (N + 1)

    for i in range(N, 0, -1) :
        if days[i][0] != 0 and days[i][0] > max_happy :
            max_happy = days[i][0]
        if days[i][1] != 0 and days[i][1] < min_fatigue :
            min_fatigue = days[i][1]

        old[i] = (max_happy, min_fatigue)

    # 최적의 K 찾기
    cnt = -1
    for k in range(N - 1, -1, -1) : # k는 젊은 날
        youth_happy = youth[k][0]
        youth_fatigue = youth[k][1]
        old_happy = old[k+1][0]
        old_fatigue = old[k+1][1]


        if youth_happy > old_happy and youth_fatigue < old_fatigue :
            cnt = max(cnt, k)

    print(cnt)

main()

1. 상수 및 입력 준비

 

INF = 1 << 32

• INF는 $2^{32}$ 값을 의미하며, 이후 "최소값"을 갱신할 때 초기값으로 사용됨

def main() :
    N = int(input())
    days = [(0, 0)] # 1-based indexing을 위한 더미 데이터

• 첫 줄에서 전체 날짜 수 N을 입력
• days 리스트의 첫 원소로 (0, 0)을 넣어 인덱스를 1부터 시작할 수 있도록 하기 위함.

---

2. 입력 데이터 받기

# 각 날짜별 행복도와 피로도 입력
for _ in range(N) :
    u, v = map(int, input().split())
    days.append((u, v))

• $N$일 동안 각 날짜의 행복도 $u$와 피로도 $v$를 입력받아 days 리스트에 순서대로 저장

---

3. 청춘(young) 배열 계산 (앞에서부터 누적)

max_happy = -1
min_happy = INF
max_fatigue = -1
min_fatigue = INF

# youth 배열 계산 (앞에서부터)
youth = [(0, 0)]
for i in range(1, N + 1) :
    if days[i][0] != 0 and days[i][0] < min_happy :
        min_happy = days[i][0]
    if days[i][1] != 0 and days[i][1] > max_fatigue :
        max_fatigue = days[i][1]
    youth.append((min_happy, max_fatigue))

• 목적 : 날짜 1일부터 $i$일까지의 구간에서, 유효한(0이 아닌) 값들을 기준으로
  
  • 최소 행복도 (min_happy)
  • 최대 피로도 (max_fatigue)
    를 각각 갱신하여 youth[i]에 저장
• 동작 : 
  • 매 날짜마다, 만약 행복도가 0이 아니면서 현재까지의 min_happy보다 작으면 갱신.
  • 피로도의 경우, 0이 아니면서 현재까지의 max_fatigue 보다 크면 갱신
  • 이렇게 하면 youth[i] = (현재 구간 내 최소 행복도, 현재 구간 내 최대 피로도)가 됨

참고 : 여기서 0인 값은 "유효한" 데이터로 취급되지 않으므로, 업데이트에서 제외된다. 

---

4. 노년(old) 배열 계산 (뒤에서부터 누적)

# old 배열 계산 (뒤에서부터)
old = [(0, 0)] * (N + 1)

for i in range(N, 0, -1) :
    if days[i][0] != 0 and days[i][0] > max_happy :
        max_happy = days[i][0]
    if days[i][1] != 0 and days[i][1] < min_fatigue :
        min_fatigue = days[i][1]

    old[i] = (max_happy, min_fatigue)

• 목적 : 날짜 $i$로부터 $N$일까지의 구간에 대해, 유효한(0이 아닌) 값들을 기준으로
  
  • 최대 행복도 (max_happy)
  • 최소 피로도 (min_fatigue)
    를 각각 갱신하여 old[i]에 저장
• 동작 : 
  
  • 뒤쪽(날짜 $N$부터 1까지)에서 순회하면서, 행복도가 0이 아니고 현재까지의 max_happy보다 크면 갱신
  • 피로도의 경우, 0이 아니면서 현재까지의 min_fatigue보다 작으면 갱신
  • 결과적으로, old[i] = (날짜 $i$부터 $N$까지의 최대 행복도, 최소 피로도) 가 된다.

---

5. 최적의 분할점 $k$ 찾기

# 최적의 K 찾기
cnt = -1
for k in range(N - 1, -1, -1) : # k는 젊은 날
    youth_happy = youth[k][0]
    youth_fatigue = youth[k][1]
    old_happy = old[k+1][0]
    old_fatigue = old[k+1][1]


    if youth_happy > old_happy and youth_fatigue < old_fatigue :
        cnt = max(cnt, k)

• 분할의 개념 :  전체 기간을 두 부분으로 나눕니다.
  • 젊은 시절 (청춘) : 날짜 1일부터 $k$일까지
  • 노년 : 날짜 $k + 1$일부터 $N$일 까지
• 조건 해석 : 
  • youth_happy > old_happy : 청춘 구간의 최소 행복도가 노년 구간의 최대 행복도보다 커야함.
    • 이는 모든 청춘 날들이 노년 날들보다 행복도가 높아야 함을 의미함
  • youth_fatigue < old_fatigue : 청춘 구간의 최대 피로도가 노년 구간의 최소 피로도보다 작아야 함.
    • 이는 청춘 날들이 노년 날들보다 피로도가 낮아야 함을 의미함.
• 동작 : 
  • $k$를 $N - 1$ 부터 0까지 (역순) 순회 하면서 위 조건을 만족하는지 검사
  • 조건을 만족하면, cnt를 현재까지의 최대 $k$ 값으로 갱신
  • 만약 어떤 $k$도 조건을 만족하지 않는다면 cnt는 초기값 $-1$로 남음.

주의 : 

• $k = N$인 경우에는 노년 구간이 없으므로 고려하지 않고, $k$는 $N - 1$ 이하의 값만을 검사
• 0값은 업데이트에 사용되지 않으므로, 실제 비교는 유효한(0이 아닌) 데이터에 대해서만 이뤄짐.

 

 

전체적인 요약

1. 입력:
   • $N$일 동안의 행복도와 피로도 데이터를 입력받고, 1-based 인덱스로 관리합니다.
2. 청춘 배열 계산 (앞에서부터):
   • 날짜 1일부터 $i$일까지의 구간에 대해, 유효한 행복도 중 최소값과 유효한 피로도 중 최대값을 기록합니다.
3. 노년 배열 계산 (뒤에서부터):
   • 날짜 $i$부터 $N$일까지의 구간에 대해, 유효한 행복도 중 최대값과 유효한 피로도 중 최소값을 기록합니다.
4. 분할점 $k$ 탐색:
   • 날짜 1부터 $k$까지를 청춘, $k+1$부터 $N$까지를 노년으로 보았을 때,
     • 청춘의 최소 행복도가 노년의 최대 행복도보다 크고,
     • 청춘의 최대 피로도가 노년의 최소 피로도보다 작아야 합니다.
   • 이러한 조건을 만족하는 $k$들 중 최대값을 찾습니다.
5. 출력:
   • 조건을 만족하는 최적의 $k$를 출력하며, 없다면 $−1$을 출력합니다.