17204번: 죽음의 게임(python)

문제

중앙대학교 소프트웨어대학 새내기들을 맞이하게 된 17학번 김영기는 두 학번이라는 차이를 극복하기 위해 새내기들과 친해지려고 노력하고 있다. 그 노력 중 하나는 바로 새내기들과의 술자리에 참여하는 것이다. 그러나 혼자 가기에 민망했던 영기는 동기 보성이를 꼬셔 같이 술자리에 참석했다. 새내기들과 같이 술을 마시게 된 영기와 보성이는 분위기가 가라 앉을 때쯤 The Game of Death라고 불리는 죽음의 술게임을 제안한다.

죽음의 게임의 룰은 간단하다.

게임에 참여하는 N명의 사람들은 원탁에 둘러앉게 된다. 게임을 시작하는 사람은 0번, 그 오른쪽 사람은 1번, 그 오른쪽은 2번, N-1번의 오른쪽 사람은 다시 0번이 된다.

0번이 "신난다! 아싸 재미난다! 아싸 더 게임 오브 데! 스!" 라고 외침과 동시에, 모든 사람들은 각각 테이블에 둘러 앉은 사람들 중 한 명을 지목한다. 그리고 나서 0번은 임의의 양의 정수 M을 외친다.

그 다음, 0번은 "1"이라고 말한다. 이때 "1"이라고 말한 사람이 지목한 사람은 "2"라고 말하고, "2"라고 말한 사람이 지목한 사람은 "3"이라고 말하고, 같은 방식으로 반복해 M까지 말하게 된다. 이때 마지막으로 M이라고 말한 사람이 지목한 사람은 벌주를 마시게 된다.

새내기에게 벌주를 마시게 하기에는 죄책감이 들었던 영기는 동기인 보성이를 공격하기로 결심했다. 게임 참여자들간에 지목을 완료한 상태가 주어질때, 보성이가 벌주를 마시기 위해 영기가 불러야 하는 가장 작은 양의 정수 M을 보성이 몰래 귀띔해 주도록 하자.

김영기는 게임을 제안하였기에 자연스럽게 0번이 된다.

 

입력

첫 번째 줄에 게임에 참여하는 사람의 수 N(3 ≤ N ≤ 150)과 보성이의 번호 K(1 ≤ K ≤ N - 1)가 공백을 두고 주어진다.

두번째 줄부터 N줄에 걸쳐 i(0 ≤ i ≤ N - 1)번 사람이 지목하는 사람의 번호 ai(0 ≤ ai ≤ N - 1)가 주어진다. 자기 자신을 지목하는 경우도 존재할 수 있다.

 

출력

영기가 말해야 하는 가장 작은 양의 정수 M을 출력한다. 만약 어떤 방법으로도 보성이가 걸리지 않는다면 -1을 출력한다.

예제 입력 

5 3
1
3
2
1
4

예제 출력 

2

접근방법 / 문제풀이

문제를 보면 0번째 사람이 n번째 번호를 가진 사람을 선택하고 n번째 번호를 가진 사람은 m번째 번호를 가진 사람을 선택하고 이걸 반복하다가 입력값의 오른쪽 번호를 가진 사람이 지목받으면 몇번만에 그 사람이 선택됐는지를 출력하는 문제다.

옛날엔 실버문제만 봐도 덜덜 떨던 나,, 이제 구글링도 없이 혼자 뚝딱 잘 해내는 거 꽤나 기특해 ^^(구글링 필요한 실버문제도 많음)

보자마자 지목받은 사람의 번호를 가진 리스트 인덱스로 이동해야한다는 걸 깨닫고 <newnum=numlist[newnum]> 이 코드를 먼저 생각해 냈다.

그리고 또 필요한 게 몇번만에 지목받았는지 count를 셀 필요가 있었다. 그래서 for문을 돌려가며 list를 하나씩 탐색해 그 번호로 이동하면서 count를 1씩 올려주면 되지 않을까 생각하였다. 그러다가 원하는 번호의 사람이 지목받으면 그 count를 출력하고 break를 통해 멈춰줘야 한다고 생각하였다.

그리고! 우리 스터디에서 알게된 for else문을 사용해 보았다. else는 if에만 쓸 수 있는 줄 알았지만 저번에 은석님이 우연히 for else문을 썼다가 코드가 잘 작동하는 걸 보고 스터디에서 같이 찾아보고 알게 된 for else문!! 

for문이 돌아가다가 break를 만나면 else문으로 빠지지 않고 break를 안 만나면 실행되게 된다. newnum과 num이 다를 때 (다른 사람이 지목받았을 때) if문으로 돌아가다가 newnum과 num이 같을 때(지목받아야 하는 사람이 지목받았을 때) break문을 만나게 되는데 if문만 돌아가다가 for문이 끝나는 경우, 그러니까 지목받아야 하는 사람이 어떤 경우에도 지목받지 못하는 경우에는 break문을 만나지 못하기 때문에 for else로 빠지게 된다. 그렇게 작성한 코드는 아래와 같다.

t,num=map(int,input().split())
numlist=[]
for i in range(t):
    a = int(input())
    numlist.append(a)
newnum=0
count=0
for i in range(t):
    if newnum != num:
        newnum=numlist[newnum]
        count+=1
    else:
        print(count)
        break
else:
    print(-1)

메모리: 31256KB  시간: 48ms