[Python] 백준 23351번_물 주기

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

23351번: 물 주기

 

• 일직선으로 놓여진 N개의 화분에 캣닢이 하나씩 심어져 있음
• 각 화분은 초기에 K만큼의 수분을 머금고 있고, 매일 아래와 같은 일이 순서대로 일어남
  • 1) 집사가 연속된 A개의 화분에 물을 줌. 이 때 물을 준 화분의 수분은 B만큼씩 증가
  • 2) 모든 화분의 수분이 1씩 감소
  • 3) 수분이 0이 된 화분에 있는 캣닢은 죽음
• 모든 캣닢이 살아 있는 기간이 최대한 길어지도록 물을 줄 때, 첫 캣닢이 죽는 날짜를 출력
• 첫 날은 1일

• 입력
  • 첫째 줄에 자연수 N, K, A, B가 공백을 사이에 두고 주어짐 (2≤N≤100, 1≤K≤100, 1≤A×B<N, A는 N의 약수)
• 출력
  • 모든 캣닢이 살아 있는 기간이 최대한 길어지도록 물을 줄 때, 첫 캣닢이 죽는 날짜를 출력
• 시간 제한: 1초
• 메모리 제한: 512 MB

 

"""
입출력 예시)

(예제 입력 1) 
6 3 2 2 -> 5

(예제 입력 2)
2 2 1 1 -> 3
"""

 

 

## 의사코드 ##

# 모든 캣닢이 살아 있는 기간이 최대한 길어지도록 물을 줄 때
# -> 수분이 작은 순서대로 화분을 정렬

# while 화분에 0이 없을 동안:
#     모든 조건 수행 후 
#     화분.sort()
#     날짜 += 1

 

 

 

첫 번째 시도

 

n, k, a, b = map(int, input().split())
# 각 화분은 초기에 k만큼의 수분을 머금고 있음
pots = [k for _ in range(n)] 
day = 0 # 물을 준 날짜

# 모든 캣닢이 살아 있을 동안 반복
while 0 not in pots:
    # 연속된 a개의 화분의 수분이 b만큼 증가 
    for i in range(a):
        pots[i] += b 
    # 모든 화분의 수분 1씩 감소
    for p in pots:
        p -= 1
    # 수분이 작은 순서대로 화분을 오름차순 정렬
    pots.sort()
    # 날짜 + 1
    day += 1

print(day)

-> 시간 초과

 

 

 

통과한 코드

 

n, k, a, b = map(int, input().split())
# 각 화분은 초기에 k만큼의 수분을 머금고 있음
pots = [k for _ in range(n)] 
day = 0 # 물을 준 날짜

# 모든 캣닢이 살아 있을 동안 반복
while 0 not in pots:
    # 연속된 a개의 화분의 수분이 b만큼 증가 
    for i in range(a):
        pots[i] += b 
    # 모든 화분의 수분 1씩 감소
    for i in range(n):
        pots[i] -= 1
    # 수분이 작은 순서대로 화분을 오름차순 정렬
    pots.sort()
    # 날짜 + 1
    day += 1

print(day)

-> 모든 화분의 수분 1씩 감소할 때, for p in pots가 아닌 for i in range(n)으로 수정

 

• 모든 캣닢이 살아 있는 기간이 최대한 길어지도록 하기 위해 수분이 작은 순서대로 정렬해야 한다는 점이 포인트
  • 탐욕 알고리즘은 구현할 때 정렬도 함께 사용된다는 점 잊지 말기 

 

• cf) while min(pots) != 0 이 while 0 not in pots 보다 4 ms 더 빠름

 

 

 

 

 

참고)

 

https://hyuuny.tistory.com/135

[algorithm] 백준 23351 - 물 주기 (파이썬)

 

https://velog.io/@seungjun123/%EB%B0%B1%EC%A4%80-23351%EB%B2%88-%EB%AC%BC-%EC%A3%BC%EA%B8%B0-Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] 23351번 물 주기 (Python 파이썬)