[2022 Yokohama Regional] Make a Loop (BOJ 27421)

링크
문제를 요약하겠습니다.

• 사분원 둘레 $n$개가 주어집니다.
• 이들을 잘 돌리고 조합하여 하나의 폐회로를 완성해야 합니다.
• 단, 두 개의 사분원 둘레가 만나는 부분은 부드럽게 이어져야 합니다.
• $4\le n\le 100;$ $1\le r\le 10\,000$
• Yes / No로 답해주세요.

 
접근 1
 

• naïve한 여러 방법들이 떠오릅니다
• 방향 고정 등으로 중복을 획기적으로 줄일 수 있을까요? → 그다지..
• DP가 계속 맴도는데.. 좌우상하 DP로 점화식을 세워 볼까요? → 역시나 역부족..
  • 필요한 알짜 x, 알짜 y를 상태에 포함? → 결국 좀 애매합니다..
• 이동 범위를 확인할 수 있을까요? → 딱히 연속적이지 않아서 무의미해 보입니다..
• 다만.. 45도로 돌려볼 수 있을까요? → x,y를 복합적으로 고려해야 하는 상황에서 독립적인 상황으로 바뀝니다!

 
관찰 1

 

• 45도로 돌리고 나면 x, y가 좀 독립적입니다
• x 방향 이동을 볼록한 방향에 따라 다른 색으로, y 방향도 이동을 볼록한 방향에 따라 다른 색으로 부여하면, 같은 방향 이동끼리의 부드러운 연결을 그저 색깔을 번갈아 칠하는 것으로 이해할 수 있습니다!
• 위로 볼록한 x 방향 이동을 빨간색, 아래로 볼록한 y 방향 이동을 파란색으로 생각해봅시다.
• 그럼 그림과 같이 y 방향 이동의 자취의 위쪽에는 빨간색 이동이 연결되고, 아래쪽에는 파란색 이동이 연결된다는 사실도 알 수 있습니다.

 
관찰 2

• 그리고 어떤 폐회로던 잘 변형하여 결국 다음 두 가지 종류의 폐회로로 환원할 수 있다는 걸 알 수 있습니다.

• 이때, 왼쪽에서는 x 방향 이동을 위쪽과 아래쪽 두 그룹으로 나눌 수 있는데, 다음 조건을 만족해야 합니다.
  
  • 각 그룹의 크기는 홀수
  • 길이 총합은 동일
• 오른쪽에서는 x 방향 이동을 위쪽->아래쪽과 아래쪽-> 위쪽 두 그룹으로 나눌 수 있는데, 다음 조건을 만족해야 합니다.
  • 각 그룹의 크기는 짝수
  • 길이 총합은 동일
• 또한 왼쪽에서는 규칙이 y 방향에서도 똑같이 적용될 것입니다.
• 그럼 오른쪽은..? 결국 오른쪽도 구체적으로 나타내면 다음과 같죠.

• 따라서 y 방향에서도 규칙이 똑같이 적용됩니다.

 
종합하면,

• 짝수 크기 그룹 4개로 쪼개되, 둘씩 길이 합이 같거나
• 홀수 크기 그룹 4개로 쪼개되, 둘씩 길이 합이 같아야 합니다.
• $n=4$일때는 예외 상황이 있을 수 있으니 이건 따로 처리하고,
• $n$이 홀수일 때는 당연히 안 되니까 쳐낼 수 있습니다.
• 다시 말하면, $n\ge 6$인 짝수만 다루면 됩니다.

 
관찰 3

• 그런데 길이 합이 같다는 조건을 생각해보면, 길이 총합의 절반과 길이가 같은 상태가 2개 이상 존재한다는 것으로 이해할 수 있습니다.
• 따라서 그룹 4개를 서로 다른 방향끼리 둘씩 묶어서 생각할 수 있습니다.
• 그런 과정을 거쳐서 해석하면, 두 가지 그룹을 찾은 후, 그 둘의 집합의 교집합을 통해 집합을 4개로 쪼개어 해결할 수 있습니다.

 

마무리

• 좀 풀이가 어수선했는데요...
• 궁금한 점은 댓글로 남겨주시면 알려드립니다.
• 노트 사진이랑 코드 올리고 마무리하겠습니다.

왼쪽 하단은 다른 문제의 풀이입니다

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define mup(x,y) x = min(x,y)

const int N = 103, R = 10'003;
int n, a[N];
int odd[N*R], even[N*R];

int main() {
    scanf("%d", &n);
    rep(i,1,n) scanf("%d", &a[i]);
    if (n == 4) {
        bool ans = (a[1]==a[2]&&a[3]==a[4]);
        ans |= (a[1]==a[3]&&a[2]==a[4]);
        ans |= (a[1]==a[4]&&a[2]==a[4]);
        printf(ans ?"Yes" : "No");
        return 0;
    }
    if (n%2) puts("No"), exit(0);
    int sum = accumulate(a+1,a+n+1,0);
    even[0] = 1;
    rep(i,1,n) {
        per(j,1,sum) {
            if (j >= a[i]) {
                even[j] += odd[j-a[i]];
                odd[j] += even[j-a[i]];
                mup(even[j],5);
                mup(odd[j],5);
            }
        }
    }
    if (sum%2) puts("No"), exit(0);
    if (even[sum/2] >= 4) puts("Yes");
    else puts("No");
}

 
UPD - 정해의 접근은 저랑 상이하네요. 관찰 위주로 심플하게 정리되어 있습니다. 참고하세요 :) https://icpc.iisf.or.jp/past-icpc/regional2022/commentaries2022.pdf