오늘의 코드. 4일차 (백준/25642번 젓가락 게임)

이런 알고리즘으로 풀면 바로 답이 나오고, 이런 수학 공식을 쓰면 답이 바로 나오는 문제보다는
조금 더 생각하게 되는 문제를 찾아보았다.

 

Baekjoon / Problem No. 25642  (젓가락 게임)

 

Problem

용태와 유진이가 재미있는 젓가락 게임을 하려고 한다. 게임의 진행은 다음과 같다.

1. 용태가 한 손에 펴고 시작할 손가락의 개수 A( 1 ≤ A ≤ 4 )를 정한다.
2. 유진이가 한 손에 펴고 시작할 손가락의 개수 B( 1 ≤ B ≤ 4 )를 정한다.
3. 용태부터 시작해서 서로 번갈아가면서 상대를 공격해서 손가락을 더 펴게 한다. 만약 X 개의 손가락을 펴고 있는 사람이 상대를 공격하면, 상대는 X 개의 손가락을 더 펴야 한다.
4. 다섯 손가락 이상을 펴야 하는 사람이 패배한다. 게임은 한 손만을 사용해 진행하는 것에 유의한다.

예를 들어 용태가 1개, 유진이가 2개의 손가락을 편 채로 게임을 시작한다면 게임의 진행은 다음과 같다.

1.  (1,2)→(1,3) 용태가 선공이므로 유진이를 공격하면 유진이는 1개의 손가락을 더 편다.
2.  (1,3)→(4,3) 유진이가 용태를 공격하면 용태는 3개의 손가락을 더 편다.
3.  (4,3)→(4,7) 용태가 유진이를 공격하면 유진이는 7개의 손가락을 펴야 하고, 유진이가 패배한다.

용태와 유진이가 한 손에 펴고 시작하는 손가락의 개수가 주어졌을 때, 그대로 게임을 플레이한다면 누가 이기게 될까?

 

Input

첫째 줄에 용태가 한 손에 펴고 시작할 손가락의 개수 A( 1 ≤ A ≤ 4 ) 와 유진이가 한 손에 펴고 시작할 손가락의 개수

B( 1 ≤ B ≤ 4 ) 가 주어진다.

 

Output

용태와 유진이가 게임을 플레이했을 때 용태가 이기게 된다면 yt 를, 유진이가 이긴다면 yj 를 출력한다.

---

Solution 

위 문제의 상황을 한번 표로 정리해보자.

공격한 사람	턴	용태의 개수 X	유진이의 개수 Y
초기상태	0	x	y
용태	1	x	x+y
유진	2	2x+y	x+y
용태	3	2x+y	3x+2y

 

표의 맨 오른쪽 아래를 보면 3번째 턴까지 가면 이미 유진이는 반드시 패배하게 되어있다.

(손가락의 개수는 무조건 1 이상이다.)

 

우리는 용태를 응원하는 마음으로 한번 바라보자. 용태가 이기는 경우의 수는

1. 처음 공격 때 유진이를 탈락시킨다. ( x + y > 5 ) 의 경우
2. 2번째 턴에 공격받을 때까지 버틴다. ( 2x + y < 5 ) 의 경우

2번째 턴까지 버티게 되면 이미 다음턴의 공격으로 승리는따놓은 당상. 즉, 3턴까지 안가더라도 2턴에서 버틴 시점에서 이미 '필승점'에 도달했다고 볼 수 있다. 

 

위의 연립부등식을 풀어보자. 

주어진 조건식을 보면 

수식 작성 사이트 <HostMath> 를 이용하여 수식을 작성했다.

 

다음 조건을 만족하는 정수해 를 가지는 ( X, Y )가 용태가 이기는 경우라고 볼 수 있다. 그래프로 그려보자.

기하학 계산기 프로그램 <GeoGebar> 를 이용하여 그려보았다.

 

용태가 이기는 지점을 푸른색 동그라미로, 유진이가 이기는 지점을 붉은색 X표시로 칠해보았다.

(용태는 치사하게 75%의 확률로 자신이 이기는 게임을 한 것이다. 불쌍한 유진이...) 

 

위의 식을 만족하는 범위내의 X와 Y를 찾으면 되는 문제이므로, If 조건식에 그대로 반영해주면 누가 이길지 알 수 있다. 

---

Code

#include <cstdio>

int main()
{
    int x, y;
    scanf("%d %d", &x, &y);

    if(y >= ((-1 * x) +5) || y < ((-2 * x) + 5) )
        printf("yt");
    else
        printf("yj");
}

 

 

물론, 이미 용태가 이기는 지점을 모두 알고 있기 때문에 꼼수를 써서 유진이가 이기는 부분을 제외한 모든 부분을 용태가 이기는 부분으로 생각해 다음과 같이 풀 수도 있다. (조건이 바뀐다면 당연히 사용할 수 없다.)

#include <cstdio>

int main()
{
    int x, y;
    scanf("%d %d", &x, &y);
    if((x==1 && y==3)||(x==2 && y==1)||(x==2 && y==2)||(x==3 && y==1))
        printf("yj");
    else
        printf("yt");
}

 

소스코드 사진이다.

---

Review

굉장히 쉬운 문제였고, 풀이과정이 바로 떠올랐지만, 이 문제는 다른문제와 달리 알고리즘이나, 그렇다고 대단한 수학적 지식이 필요한 문제가 아니다. 그렇기에 순전히 본인의 힘만으로 (웹서핑 없이) 어떻게 풀지 스스로 생각할 수 있었다.

 

컴퓨터로 코드를 짜는 것은 글씨를 직접 쓰는 것과 다르게 소스코드만 봐서는 이게 누가 쓴 코드인지 알 수가 없다.

누군가가 짜놓은 완벽한 소스코드를 이것 저것 긁어와서 문제를 푸는것도 중요하지만

내가 생각할 수 있는 힘을 키우지 않는다면, 과연 그것을 내가 '생각해서' 짠 코드라고 말할 수 있을까?

 

분명 다른이의 아이디어를 참고하는것도 문제해결의 측면에서는 도움이 되는 일이다.

그런 아이디어를 내가 이해하고 짜느냐와, 무지성으로 복붙을 하느냐는 다른 차원의 문제이다.

 

자신이 직접 생각하고, 필요한 때에 타인이 만든 코드를 '도구'로 '참고'해야한다고 생각한다.

내가 타인의 코드를 생각없이 복사 붙여넣기나 해서 문제를 푸는 '도구'가 되지는 말아야 할 것이다.

물론 이는 되게 어려운 일이다.

 

문제 하나에 너무 나갔나. 아무튼 그렇다.