[ BOJ / Python ] 14493번 과일노리

9392 단어 pythonbojboj

이번 문제는 소요시간을 누적시키고, 현재 기다린 시간에서 해당 구간의 A+B를 나눴을 때의 나머지가 B와 같아질 때 다음 구간으로 넘겨가며 누적된 소요시간을 구해 해결하였다.

처음에는 기다린 시간 누적을 1씩 더했고 정답은 나왔지만 성능이 좋지는 않았다.

  • n을 입력받는다.
  • 구간 별 A와 B의 정보를 저장할 bot배열을 선언한다.
  • 현재 소요시간을 나타내는 변수 cur은 0으로 정의한다.
  • 0부터 n까지 반복하는 i에 대한 for문을 돌린다.
    -> a와 b를 입력받은 뒤, a와 b를 포함하는 배열을 bot배열에 넣어준다.
  • 첫번째 구간은 무조건 B만큼 기다려야 하므로 cur에 bot[0][1], 즉 B[0]을 더해준다.
  • while문에서 구간을 나타내줄 변수 i를 1로 정의한다. (이미 첫번째 구간은 진입했으므로)
  • i가 n보다 작을 동안 반복하는 while문을 돌린다.
    -> 소요시간의 흐름을 나타내기 위해 cur에 1을 더해준다. (다음 구간으로 이동하는데에 1초가 소요되고, 이동하지 않고 기다려도 1초가 소요되므로)
    -> 만약 cur%(bot[i][0]+bot[i][1])이 bot[i][1]보다 크거나 같다면 다음 구간으로 이동 가능하므로 i를 1 증가시킨다.
  • cur+1을 출력한다. (마지막 구간으로 이동하는데에 걸리는 시간 1초를 더해야 하므로)
n=int(input())
bot=[]
cur=0
for i in range(n):
    a, b=map(int, input().split())
    bot.append([a, b])
cur+=bot[0][1]
i=1
while i<n:
    cur+=1
    if cur%(bot[i][0]+bot[i][1])>=bot[i][1]:
        i+=1
print(cur+1)

정답처리는 됐지만 4836ms가 소요됐다. 줄일 수 있는 방법을 생각해보다가 다음 단계로 넘어가지 못할 경우 부족한 시간만큼 바로 소요시간에 추가하도록 구현해보았다.

  • n을 입력받는다.
  • 구간 별 A와 B의 정보를 저장할 bot배열을 선언한다.
  • 현재 소요시간을 나타내는 변수 cur은 0으로 정의한다.
  • 0부터 n까지 반복하는 i에 대한 for문을 돌린다.
    -> a와 b를 입력받은 뒤, a와 b를 포함하는 배열을 bot배열에 넣어준다.
  • 첫번째 구간은 무조건 B만큼 기다려야 하므로 cur에 bot[0][1], 즉 B[0]을 더해준다.
  • while문에서 구간을 나타내줄 변수 i를 1로 정의한다. (이미 첫번째 구간은 진입했으므로)
  • i가 n보다 작을 동안 반복하는 while문을 돌린다.
    -> 소요시간의 흐름을 나타내기 위해 cur에 1을 더해준다. (다음 구간으로 이동하는데에 1초가 소요되고, 이동하지 않고 기다려도 1초가 소요되므로)
    -> 만약 cur%(bot[i][0]+bot[i][1])이 bot[i][1]보다 크거나 같다면 다음 구간으로 이동 가능하므로 i를 1 증가시킨다.
    -> 그렇지 않다면 cur에 bot[i][1]-cur%(bot[i][0]+bot[i][1])-1을 더해준다. 마지막에 1을 빼는 이유는 다음 반복에서 1이 더해질 것이기 때문이다.
  • cur+1을 출력한다. (마지막 구간으로 이동하는데에 걸리는 시간 1초를 더해야 하므로)

Code

n=int(input())
bot=[]
cur=0
for i in range(n):
    a, b=map(int, input().split())
    bot.append([a, b])
cur+=bot[0][1]
i=1
while i<n:
    cur+=1
    if cur%(bot[i][0]+bot[i][1])>=bot[i][1]:
        i+=1
    else:
        cur+=(bot[i][1]-cur%(bot[i][0]+bot[i][1])-1)
print(cur+1)


시간이 2208ms로 절반 이상 줄어든 것을 확인할 수 있다.

좋은 웹페이지 즐겨찾기