BOJ 27421 Make a Loop

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/27421
• 번역

문제

#

Taro는 장난감 철도 선로 세트를 가지고 놀고 있습니다. 모든 선로는 직각 중심각(90도 각도)을 가진 호 모양이지만, 반지름은 다양합니다. Taro는 이 모든 선로를 사용하여 하나의 루프를 만들려고 합니다. 여기서 선로 세트가 하나의 루프를 형성한다는 것은 모든 선로의 양 끝이 다른 선로와 부드럽게 연결되고, 모든 선로가 직접 또는 간접적으로 다른 모든 선로와 연결되어 있을 때를 의미합니다. Taro가 이것을 달성할 수 있는지 여부를 알려주세요.

선로는 임의의 순서로 연결할 수 있지만, 인접한 선로의 방향에 따라 방향이 제한됩니다. 부드럽게 연결되어야 하기 때문입니다. 예를 들어, 기차가 동쪽으로 들어와서 90도 회전하여 북쪽으로 나가도록 선로를 배치하면, 다음 선로는 기차가 북쪽으로 들어와서 90도 회전하여 동쪽 또는 서쪽으로 나가도록 배치해야 합니다(그림 F.1). 고가 건설이 가능하므로 선로는 서로 교차하거나 겹칠 수도 있습니다.

입력

#

입력은 다음 형식의 단일 테스트 케이스로 구성됩니다.

n
r_1 ... r_n

$n$은 선로의 개수를 나타내며, $4≤n≤100$을 만족하는 짝수입니다. 각 $r_i$​는 $i$번째 선로의 반지름을 나타내며, $1≤r_i≤10000$을 만족하는 정수입니다.

출력

#

모든 선로를 사용하여 하나의 루프를 만들 수 있으면 Yes를 출력하고, 그렇지 않으면 No를 출력합니다.

🧐 관찰 및 접근

#

• 흠 일단… 예제 2번에서 볼 수 있듯이, $1 ,1 ,1$ 은 $3$으로 쓸 수 있다.
  • 홀수개라면 합쳐서 크기를 늘리는게 가능하다.
• 음… $3, 1, 1, 1$이 있다고 치고, 안쪽으로 말면서 하면 이걸 $2$로도 해석할 수 있는데…
  • 예제 3번이 아마 $10, 10, 2, 5, 1$을 이용해서 $(0, 0) -> (14, 16) -> (113, -83) -> (98, -98) -> (0, 0)$이 된걸 보면, 조금 자유롭게 쓰는것도 문제 없는것 같다.
• 결국 각 호를 이용해서 $(r, r), (r, -r), (-r, r), (-r, -r)$ 의 선택을 하는거 같은데..
  • 이때 서로 마주보는 느낌의 호인 원의 왼쪽위 / 오른쪽위, 왼쪽아래 / 오른쪽아래의 개수가 맞아야 한다!
• 음, 관찰을 좀더 해보니, 저 움직임의 선택에서 반대로 가기 $(r_1, r_1) \rightarrow (-r_2, -r_2)$ 같은거 빼고는 좀 자유롭게 되는거같은데.
• 조금 더 쉽게 생각하기 위해 호가 아니라 선분이라고 생각하고, 전반적으로 $45\degree$ 돌려보자.
  • ![[Drawing 2026-02-11 15.38.06.excalidraw.png]]
  • 위와 같은 그림으로 해석할 수 있겠다.
  • 결국 각 선로를 상하좌우 $4$개의 그룹으로 나누고, $S_{right} = S_{left}, S_{up} = S_{down}$을 만족해야 할 것 같다.
  • 회로를 만들기 위해선 상하좌우 각 그룹에 하나 이상씩은 들어있어야 할 것 같다.
  • 그런데 첫번째 친구가 원의 왼쪽위 모양의 $(r, r)$ 그룹이었다고 생각해보자. 이 친구 다음에는 $(r, r), (-r, r)$이 올 수 있는걸 보니.. 이어진 개수에 따라 다음 친구가 (우, 하) 에서 선택할 수 있을지 (우, 상)에서 선택할 수 있을지가 갈린다.
    • 경로가 스무스할 조건이 어려운데… (우 우 상 좌 하) 도 모양이 스무스하지 않다.
      • 아, 전반적으로 같은 모양을 연달아 사용할때 시계 / 반시계 모양의 패리티가 바뀌는 것 같다.
    • 일단 돌리기 전에 호로 해석할때, 위를 바라보는 꼭짓점을 0, 오른쪽을 1, 아래를 2, 왼쪽을 3이라고 하자.
      • $(r, r)$ 간선은 $0 \leftrightarrow 1$ 을 왔다갔다 한다.
      • $(r, -r)$ 간선은 $1 \leftrightarrow 2$를 왔다갔다 한다.
    • 이런 느낌을 볼때,결국 오른쪽을 바라보는 꼭짓점은 $S_{r, r} + S_{r, -r}$ 번 등장하는거 같은데..
      • 이는 들어가는것 / 나가는것 포함이므로, 이는 짝수여아한다.
    • 위와 같은 방법을 반복하면, 상하좌우 4개 그룹의 패리티는 같아야한다는 결론이 나온다!
• 위 내용들을 모두 정리하자면,
  • 상 하 좌 우 4개 그룹의 패리티는 같아야하고, 각 그룹의 크기는 1 이상이어야 한다.
  • 상 그룹의 합과 하 그룹의 합은 같아야하고, 좌 그룹과 우 그룹의 합도 같아야한다.

💻 풀이

#

• 코드 (C++):

void solve(){
    int N; cin >> N;
    vector<int> R(N);
    rep(i, 0, N) cin >> R[i];

    int sum = 0;
    for(auto x: R) sum += x;
    if(sum % 2){
        cout << "No";
        return;
    }

    vector<vector<int>> DP(N+1, vector<int>(mxS, 0));
    DP[0][0] = 1;

    ll cnt = 0;
    rep(idx, 0, N){
        int x = R[idx];
        rrep(i, 0, idx+1) rep(j, 0, sum/2+1) if(DP[i][j] && j + x <= sum/2){
            if(i%2 == 1 && j + x == sum/2) cnt += DP[i][j];
            if(cnt >= 4){
                cout << "Yes";
                return;
            }
            DP[i+1][j+x] += DP[i][j];
        }
    }

    cout << "No";
}