1614. [Python]영식이의 손가락

1. 문제

 

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

1614번: 영식이의 손가락

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 구현

 

3. 파이썬 코드

 

# N 값과 check 값으로 몇번째 손가락 몇번째인지 확인
N  = int(input())
check = int(input())
# 만약 첫번째 손가락의 경우
if N == 1:
    # 1부터 시작해서 2,3,4,5,4,3,2 순으로 8번만에 돌아오기 떄문에 8*check 를 해줌
    print(8*check)
# 두번째 손가락의 경우
elif N == 2:
    # check 가 0인경우는 N에서 -1 을 해주면 된다
    if check == 0:
        print(N-1)
    # 이후 check 값이 0이 아닌경우
    else:
        # check 값이 홀수냐 짝수냐에 따라서 오른쪽에서 오는지 왼쪽에서 오는지가 달라진다.
        # 끝과 끝을 제외하고는 왔다가는 것이 아닌 편도로 값을 확인해야기 떄문에 8이 아닌 4의 배수를 조정하는 것이다.
        # 짝수와 홀수의 경우도 나뉘는데 짝수의 경우 왼쪽에서 오는 시작 값이기 때문에 check 값을 그대로 사용하여도 된다.
        # 홀수의 경우 이미 한번 지나간 후 다시 돌아오는 값이기 때문에 check에 +1 을 해준 4의 배수를 다뤄준다.
        # 손가락 위치에 따라서 두번째 손가락은 +- 1을 조작하고 세번째 손가락은 +- 2 네번째 손가락은 +- 3 다섯빼 새끼 손가락은 +4 만 해주면 된다.
        if check % 2 == 0:
            print(4*check+1)
        else:
            print(4*(check+1)-1)
elif N == 3:
    if check == 0:
        print(N-1)
    else:
        if check % 2 == 0:
            print(4*check+2)
        else:
            print(4*(check+1)-2)
elif N == 4:
    if check == 0:
            print(N-1)
    else:
        if check % 2 == 0:
            print(4*check+3)
        else:
            print(4*(check+1)-3)
elif N == 5:
    print(8*check+4)

 

4. 문제를 풀고난 후 생각

 

• 처음에 구현했던 방식은 0번 인덱스부터 4번 인덱스까지 값이랑 cnt 변수를 통해서 더해나가는 방식으로 구현했다.

N  = int(input())
check = int(input())

fingers = [0,0,0,0,0]
middle = 0
index = 0
answer = 0

while True:
    if middle == 0:
        fingers[index] += 1
        index += 1
        if index == 5:
            middle = 1
    elif middle == 1:
        if index == 5:
            index -= 2
        fingers[index] += 1
        index -= 1
        if index == 0:
            middle = 0
    if fingers[N-1] > check:
        break
    answer += 1
print(answer)

• 시간초과가 났다. 이러한 이유로 다른 방식으로 접근해야 한다는 것을 생각했고, 규칙을 찾기 시작했다.
• 각 손가락별 규칙을 찾아냈다.

ex)

=> 0번 시작 0, 1, 2, 3 ,4 ,3 ,2 ,1 이런 식으로 8개를 주기로 갯수가 증가한다.

=> 1번 시작 여기서는 홀수와 짝수로 나뉜다.( 홀수와 짝수는 방향을 의미한다 홀수는 우측에서 오는것 짝수는 왼쪽에서 오는것)

홀수 : 1, 2, 3, 4, 3, 2

짝수 : 1, 0

=> 2번 시작

홀수 : 2, 3, 4, 3

짝수 : 2, 1, 0, 1

=> 3번 시작

홀수 : 3, 4

짝수 : 3, 2, 1, 0, 1, 2

=> 4번 시작 4, 3, 2, 1, 0 ,1 ,2 ,3 또한 8개 주기로 갯수가 증가한다.

• 이런 식으로 각 위치별 어떻게 값이 변하는지 파악하였고 갯수를 세는 것은 홀수인 경우 즉 오른쪽에서 돌아오는 경우는 이미 한번 지났기 때문에 목표하는 check 값에 +1 을 해준 상태를 4로 곱해주고 거기서 4-N(index 번호기 때문에 각 숫자에서 -1 된값임)을 해준 값만큼 갯수가 변하는 것을 확인하였다.
• 이런 문제들은 직접 적어보며 규칙을 파악하는 것이 중요한 문제들이다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 구현