백준 - 영식이의 손가락(Python)

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

💡 첫번째로 생각한 것은 한번 순회하는 순서를 리스트에 넣어 다친 손가락의 위치가 들어올 때마다 count를 올려 count 다 차면 멈추는 방법을 생각했다.

n = int(input()) # 다친 손가락 위치 
m = int(input()) # 몇 번 사용할 수 있는지 

f_list = [1,2,3,4,5,4,3,2] # 손가락 세는 순서 리스트로 생성 
num_list = []

count = 0 

while count != m: # 둘 다 0일때 시작을 못함 
    for i in f_list:
        print(num_list)
        if i == n and count != m:
            count += 1
            num_list.append(i)
        elif i == n and count == m:
            break
        else:
            num_list.append(i)


print(len(num_list))

하지만 이 방법의 경우 다친 손가락을 사용할 수 없지만 첫번째 손가락이 아닌 위치를 다쳤다면 그 이전까지는 숫자를 셀 수 있는 경우를 처리하지 못한다.
=> count와 사용할 수 있는 횟수가 동일하다면 break만 하는 것이 아닌 count를 +1를 해주고 while break 조건도 m+1이 아닐때까지 반복하는 것으로 주었다.
=> 결론은 런타임 에러 .. (재귀 반복하는데 제한이 걸린 것 같아 해결 코드도 넣었지만 메모리 초과)

💡 두번째는 리스트에 숫자를 전부 넣고 그 길이를 반환해서 메모리 초과가 뜬 것 같아 리스트에 넣는 방식이 아닌 count처럼 숫자를 하나씩 올리는 방식으로 수정했다.

n = int(input()) # 다친 손가락 위치 
m = int(input()) # 몇 번 사용할 수 있는지 

f_list = [1,2,3,4,5,4,3,2] # 손가락 세는 순서 리스트로 생성 
dis = 0

count = 0 

while count != m+1: # 둘 다 0일때 시작을 못함 
    for i in f_list:
        if i == n and count == m:
            count += 1
            break 
        elif i == n and count != m+1:
            count += 1
            dis += 1
        else:
            dis += 1

print(dis)

=> 시간 초과 ..

중요한 부분을 간과했다. 사용할 수 있는 횟수가 10억으로 매우 크다.

💡 반복문으로 돌아가면서 count를 올리는 것이 아닌 규칙을 찾아 바로 계산할 수 있도록 해야한다. 1~5까지 일정한 규칙이 존재하기에 이를 활용하여 코드를 작성하였다.

위 이미지와 같이 규칙을 발견하였고 이를 수식으로 계산할 수 있도록 작성했다.

n = int(input()) # 다친 손가락 위치 
m = int(input()) # 몇 번 사용할 수 있는지 

if m == 0:
    print(n-1)

else:
    if n == 1:
        print(m*8)
    elif n == 2:
        if m % 2 == 0: # m이 짝수면 
            print((m*4)+1)
        else:
            print((m*4)+3)
    elif n == 3:
        print((m*4)+2)
    elif n == 4:
        if m % 2 == 0:
            print((m*4)+3)
        else:
            print((m*4)+1)
    else:
        print((m*8)+4)

---

📝 : 항상 조건으로 주어지는 입력 데이터의 크기를 잘 확인하고 그에 맞는 방법을 적용하여 푸는 연습을 하자