[TIL]25-01-03

문제 요약

• 각 나무가 자라는 시간이 다르며, 나무를 하나씩 심을 수 있다.
• 모든 나무가 다 자란 후에 하루를 더하여 파티를 열 수 있다.
• 모든 나무가 자라는 데 필요한 최소 날짜를 구해야 한다.

---

기본 아이디어

1. 심는 순서와 자라는 시간의 관계:

   • 나무를 심는 순서가 중요합니다. 자라는 시간이 긴 나무를 먼저 심는 것이 전체 소요 시간을 줄일 수 있습니다.
   • ( i ): 나무를 심는 날 (0일부터 시작)
   • ( trees[i] ): 나무 ( i )가 자라는 데 걸리는 시간
   • 따라서, 나무가 다 자라는 데 걸리는 시간은 ( i + trees[i] )로 계산됩니다.

2. 최적화 목표:

   • ( i +trees[i])가 가장 큰 값이 모든 나무가 자라는 데 걸리는 총 시간이 됩니다.
   • 이를 위해 나무를 자라는 시간이 긴 순서대로 심습니다.

---

풀이 과정

1. 나무 정렬:
   • 나무를 자라는 시간이 긴 순서대로 정렬합니다.
2. 각 나무의 자라는 시간 계산:
   • 나무 ( i )를 심는 데 걸리는 날 ( i )와 나무의 자라는 시간 (trees[i])를 더합니다.
   • 이를 반복하여 가장 큰 값을 찾습니다.
3. 최종 계산:
   • (max(i + trees[i])를 구하고, 모든 나무가 자란 이후 하루를 더합니다.

---

최적화된 코드

import sys

input = sys.stdin.readline

N = int(input())
trees = list(map(int, input().split()))

# 나무를 자라는 시간이 오래 걸리는 순으로 정렬
trees.sort(reverse=True)

# 각 나무가 심어진 이후 자라는 시간을 계산
max_days = 0
for i in range(N):
    max_days = max(max_days, trees[i] + i + 1)

# 모든 나무가 자란 이후 하루를 더해야 함
result = max_days+1
print(result)

---

예시

입력:

4
4 3 2 1

풀이:
1. 정렬: [4, 3, 2, 1] (이미 정렬된 상태)
2. 계산:

• 0번째 나무: ( 0 + 4 = 4 )
• 1번째 나무: ( 1 + 3 = 4 )
• 2번째 나무: ( 2 + 2 = 4 )
• 3번째 나무: ( 3 + 1 = 4 )

3. 최대값: (max(4, 4, 4, 4) = 4)
4. 결과: 최종 자라는 날 ( 4 )

출력:

5

---

시간 복잡도

• 정렬: ( O(N log N) )
• 반복문: ( O(N))
• 총 시간 복잡도: ( O(N log N) )

---

핵심 정리

• 나무를 자라는 시간이 긴 순서대로 심는 것이 핵심입니다.
• 각 나무의 자라는 시간은 ( i +trees[i])로 계산됩니다.
• (max(i +trees[i])를 기준으로 결과를 구합니다.

for문 안에서의 +1은 심는 날을 정확히 계산하기 위해 더해진 것입니다. 나무를 심는 순서가 1일부터 시작하기 때문이에요!

---

위에는 지피티가 정리해준 거고
나는 내림차순으로 정리, 로직을 맞게 짠것같지만 시간복잡도가 N^2 나 걸리는 로직이여서 시간초과가 난 것이였다.

import sys

input = sys.stdin.readline

N = int(input())

trees = list(map(int, input().split()))

trees.sort(reverse=True)

tree_max = max(trees)

bowl = list(range(tree_max, tree_max-N, -1))

cnt = 0
while cnt != N:
    for i in range(N):
        if trees[i] > bowl[i]:
            cnt = 0
            for j in range(N):
                bowl[j] += 1
            break
        else:
            cnt += 1

result = 1+bowl[0]+1
print(result)

trees 와 같은 길이의 이미 날짜가 계산된 bowl 배열을 구해놓고,
요소요소를 하나씩 비교해가며 나무가 다 자랐는지 확인하는 방식으로 구현하였다.
하나라도 다 안자라면 bowl 배열 모든 값에 +1을 해주고 또 계속 확인하는 식으로 구했다.
괜히 복잡하게 생각한 것 같기도,,
좀 더 간결하게 식이 나오게 끔 더 머리를 굴려봐야겠다..!