[Baekjoon] 노래악보 : 1392

노래악보 : 1392

---

사용언어: python

문제

현수는 학생들에게 노래를 가르치고 있다. 총 N개의 악보가 있고 i번째 악보는 Bi초로 이루어져 있다. 학생들은 0초부터 1번 악보를 따라 노래하기 시작했다. 즉 B1-1초에 1번 악보를 끝마치게 되고 B1초부터 B1+B2-1초까지 2번 악보를 따라 부르게 된다.

악보 1 1 2 3 3 3

시간 0 1 2 3 4 5

문제는 T1부터 TQ까지 Q개의 시간에 대해 대답을 하는 것인데, Ti초 때 노래하는 악보를 i번째에 출력하는 것이다.

입력

첫 줄에는 악보 수 N(1 ≤ N ≤ 100)과 질문의 개수 Q(1 ≤ Q ≤ 1,000)가 주어진다. 다음 N개의 줄에는 1번 악보부터 N번 악보까지 각 악보가 차지하는 시간(초)이 한 줄에 하나씩 주어진다. 각 악보가 차지하는 시간은 100 이하의 정수이다. 다음 Q개의 줄에는 알고자 하는 Q개의 시간(초)이 한 줄에 하나씩 주어진다. 묻는 시간 역시 정수만 주어진다.

출력

Q개에 줄에 1번 질문부터 Q번 질문까지 해당 시간(초)에 부르는 악보의 번호를 출력한다.

Think

• 먼저 문제 이해를 해보도록 하자.
• 악보의 수 만큼 해당 악보가 차지하는 시간이 한 줄에 하나씩 주어진다. 만약에 2 1 3 으로 주어지면 1번 악보는 2초동안 2번 악보는 1초 동안 3번 악보는 3초 동안 이다.
• 배열로 만들면 어떨까 생각이 들었다. 먼저 입력을 배열로 받아 이를 순회하면서 1번 악보다 2초이면 두 번 띄워주느 형식으로 배열을 만들어보면 [1,1,2,3,3,3] 이렇게 된다.
• 그 후 Q 를 순회하면서 인덱스를 불러와 주면 될거같다
• 설명이 장황했는데 쉽다.. 코드를 보자

Code

#노래악보
import sys

N, Q = map(int, sys.stdin.readline().split())

musicList = [int(sys.stdin.readline()) for _ in range(N)]
findList = [int(sys.stdin.readline()) for _ in range(Q)]

result = []
i = 1
for item in musicList:
    for _ in range(item):
        result.append(i)
    i = i + 1

for item in findList:
    print(result[item])

느낀점?

• 생각해보면 반복문을 중첩으로 쓸 필요없이 musicList를 받을 때 그냥 한번에 곱해주면 될거 같다.. 위에 처럼하면 시간복잡도만 제곱으로 증가한다..

musicList = []
for i in range(1, n+1):
    time = int(sys.stdin.readline())
    musicList += [i] * time