백준 문제풀이 : (1614) 영식이의 손가락 - c/c++

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

1614번: 영식이의 손가락

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	128 MB	Silver 3	수학 / 많은 조건 분기

 

 

문제

 

 

풀이

영식이는 엄지손가락->새끼손가락->엄지손가락 순서로 세며, 왼쪽 손을 사용하기 때문에 엄지 손가락이 1번, 새끼 손가락이 5번, 그리고 다시 엄지 손가락이 9번째, 그 후 다시 새끼 손가락이 13번째 카운트가 된다. 

 

13번 손가락을 셀 동안, 엄지와 소지는 두 번씩만 세지는 것에 검지, 중지, 약지는 세 번씩 세어진다. 가장자리에 있는 손가락이 중앙에 있는 손가락들 보다 덜 세어지는 특징을 발견할 수 있다.

 

문제 속에서 내가 확신할 수 있는, 고정될 수 있는 규칙을 하나씩 정리해나가야 그 규칙을 기준 삼아 정답을 유추해나갈 수 있다. 우선 숫자를 세는 과정 속에서 계속 반복되는 패턴을 정리해본다.

 

좌우로 왕복하며 숫자를 세기 때문에, 엄지와 소지가 각각 한 번씩, 그 외 손가락들이 두 번씩 세어지는 단위를 한 세트라고 해보자. (즉, 엄지(1), 검지(2), 중지(3), 약지(4), 소지(5), 약지(6), 중지(7), 검지(8) 가 한 세트이다. 여덜 번 세면 1세트, 열 여섯 번 세면 2세트... 이런 식으로 계산한다는 뜻이다.)

 

한 세트를 완주할 때마다 카운트는 무조건 검지(2) 손가락을 가리키고 있을 것이다. 이것이 문제 속에서 발견할 수 있는 '첫 번째 확신할 수 있는 규칙' 이다. 

 

이 규칙을 놓고, 각 손가락이 아픈 손가락일 경우를 정리해보자.

 

'다친 손가락을 셀 수 있는 횟수 = num' 이라고 쓰겠다.

 

1) 엄지(1번)가 아픈손가락이다.

아픈 손가락이 엄지일 경우, 영식이가 카운트 할 수 있는 최대 횟수는 'num*8' 번이다. 엄지 손가락을 세며 카운트를 시작하기 때문에, 무조건 한 세트가 끝날 때 가리키는 손가락이 마지막으로 카운트하는 수가 되기 때문이다. (엄지가 아픈 손가락일 경우, 카운트는 무조건 검지에서 끝난다.)

 

2) 소지(5번)가 아픈손가락이다.

엄지와 풀이법이 똑같다. 소지의 경우에는 완전히 셀 수 있는 마지막 세트까지 센 후, 다시 약지(4번) 손가락으로 돌아갔을 때가 마지막 카운트다. 즉, 'num*8+4' 번 카운트 할 수 있다.

(소지가 아픈 손가락일 경우, 카운트는 무조건 약지에서 끝난다.)

 

3) 중지가 아픈 손가락이다.

중지의 경우는 다섯 손가락 중 중앙에 위치한 손가락이기 때문에 규칙이 좀 더 단순해진다. 4번 카운트 할 때 마다 중지를 건드리는 횟수도 1씩 늘어난다. 즉 한 세트의 단위를 4회 카운트로 잡아도 충분하다.

num*4 번째 카운트가 마지막 세트이며, num*4번째에 영식이는 검지 혹은 약지를 가리키고 있을 것이다. 어느 쪽이든 다시 중지로 돌아가기 위해서는 3번의 이동이 필요하다. 하지만 중지에 도달하기 직전 손가락에서 카운트가 멈추므로, 두 번만 이동하면 된다.

 

따라서 num*4+2 가 중지일 경우 셀 수 있는 최대 카운트다.

 

4) 검지 혹은 약지가 아픈 손가락이다.

검지와 약지도 중지와 사정이 비슷하다. 두 손가락 모두 '1세트=4회 카운트' 마다 건드리는 횟수가 1씩 늘어난다. 하지만 완전히 중앙에 위치한 중지와 달리, 카운트 중인 방향에 따라 'num*4'에서 더 전진해야 할 횟수가 달라진다. 

 

만약 아픈 손가락이 검지이고, 마지막 세트에서 엄지→소지 방향으로 수를 세고 있다면 +3을 해야한다.

반대로 마지막 세트에서 소지→엄지 방향으로 수를 세고 있다면 +1 만 해도 된다.

 

아픈 손가락이 약지일 경우는 검지의 상황과 완전히 반대된다. 

 

따라서 방향으로 고려해 세트 완주 후 몇 번을 더 카운트해야하는 지 계산해줘야하는데, 방향은 num%2==0 수식으로 간단히 알아낼 수 있다. num이 짝수일 경우 완주 후 영식이는 소지→엄지 방향으로 카운트를 시작하며, 홀수일 경우는 세트 완주 후 엄지→소지 방향으로 수를 카운트하기 시작한다. 

 

 

위 규칙들을 정리해 코드로 만들면 된다.

 

 

코드 작성

#include <stdio.h>

int main() {
    long long hf=0, num=0; 
    //입력받는 값의 범위와 밑에서의 계산을 고려해 long long 타입으로 한다.
    scanf("%lld\n%lld", &hf, &num);
    
    long long count=0;
    
    if (hf==1) count=num*8; //엄지일 경우
    else if (hf==5) count=num*8+4; //소지일 경우
    else if (hf==3) count=num*4+2; //중지일 경우
    else if (hf==2) { //검지일 경우
        if (num%2==0) count=num*4+1; 
        if (num%2!=0) count=num*4+3;
    }
    else { //약지일 경우
        if (num%2==0) count=num*4+3;
        if (num%2!=0) count=num*4+1;
    }
    printf("%lld", count);
}