20.07.29 개발일지 - Frogger

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

11100번: Frogger

예전에 시도 했는데 풀지 못하고 보류 했던 문제입니다.

 

문제를 정리하자면

1. 개구리는 가로세로로만 움직일 수 있으며, 인접한 다른 개구리를 밟고 그 개구리의 다음 좌표로 이동할 수 있다.

2. 밟힌 개구리는 터져 죽는다.

3. 파리는 {(x, y) | x >= 0, y = 0}에, 개구리는 {(x, y) | x < 0, y = 모든 정수}에 위치한다,

4. 좌표별 파리를 먹을 수 있는 개구리의 최소 숫자를 출력하라. 불가능 할 시 Frogger 출력.

이렇습니다.

 

처음 접했을 때도 4 이후로 규칙을 찾을 수 없어 고민을 하다가 멈췄습니다.

그러다가 심심해서 커뮤니티에 올려봤는데, 누군가가 풀이를 적어줘서 보고 이해를 할 수 있었습니다.

 

https://github.com/marteloge/Programming-contests/blob/master/IDI%20Open/solutions/2007%20solutions.pdf

marteloge/Programming-contests

요약을 하자면 이렇습니다.

1. 개구리는 가로와 세로로만 움직일 수 있으니 개구리와 파리와의 거리는 맨하튼 거리로 표시한다.

2. 개구리들과 파리와의 가중치의 합을 구한다. Sum(K^d) = D_fly라고 봐도 무방할 것이다.

3. 위 과정을 거치면 개구리와 파리의 평면이 하나의 방정식으로 표시된다.

4. 하지만 5차 이상의 방정식은 근의공식이 존재하지 않는다.

https://m.blog.naver.com/PostView.nhn?blogId=iphone_dev&logNo=80145256483&proxyReferer=https:%2F%2Fwww.google.com%2F

N차 방정식의 일반적인 해법(=근의공식)에 대한 고찰

5. 그렇기에 우리는 거리가 0~4일 때의 값만 작성을 하고, 그 위의 값은 frogger를 출력하면 된다.

 

Mathematics 문제는 항상 이런 문제? 매력?이 있습니다.

모르면 절대로 죽었다 깨어나도 풀 수 없지만, 풀면 그 쾌감이 다른 문제보다 더 강렬합니다.

하지만 이 문제는 가중치 계산을 하는 것에 전혀 다가가지 못해서 결국 이렇게 보고 풀 수 밖에 없던 것 같습니다.

 

#include <iostream>

using namespace std;

int main()
{
    const int Mem[5] = { 1, 2, 4, 8, 20 };
    int times = 0, input = 0;
    cin >> times;
    while (times-- > 0)
    {
        cin >> input;
        if (input < 5)
        {
            cout << Mem[input] << endl;
        }
        else
        {
            cout << "frogger" << endl;
        }
    }
    return 0;
}