백준 33274: 적당한 휴식은 필수

problem solving

finding wangdo 2025. 1. 28. 23:55

일단 n이 짝수인 경우만 생각하자.

R1, R2, R3, ....., Rn, C1,C2,....., Cn이라는 총 2n개의 값은 0,1,2,3,.....,2n-1이 되어야 mex값이 최대가 될 수 있다.

문제를 풀 때 가장 먼저 생각했어야 하는 것은 R1~Rn값들의 합은 C1~Cn값들의 합과 같아야 한다는 것이다.

n=4인 경우를 예로 들어보겠다.

2n-1=7이다.

0~7까지 값들을 짝수 홀수로 분류하자.

짝수: 0 2 4 6

홀수: 1 3 5 7

이때 짝수를 앞에 있는 것 절반, 홀수를 뒤에 있는 것 절반을 가져와서 한 세트로 묶고, 나머지를 다른 한 세트로 묶으면 각 세트의 수들의 합이 14로 같아진다.

세트1: 0 2 5 7

세트2: 1 3 4 6

이런 식인 거다.

R1=0, R2=2, R3=5, R4=7

C1=1, C2=3, C3=4, C6=6

이렇게 할당해보자.

정답 행렬을 표로 그려보겠다.

내가 임의로 0들을 채워넣었다.

이제 별표표시된 네 개의 칸을 보아라.

R1+R4=C1+C4=7이기 때문에 네 ★들 중 아무데나 숫자를 임의로 하나만 넣으면 나머지 ★ 3개에 알맞은 숫자를 지정할 수 있음이 보장된다는 것을 알 수 있다.

★1에 0을 넣어보자. 그럼 자동으로 채워지는 숫자들은

이렇게 된다.

그리고 새로운 ★들이 생겼다.

위에랑 같은 규칙으로 채워주면 된다.

다 채웠다.

규칙에 맞는 행렬을 찾은 것이다.

N의 크기를 좀 더 키워보자. 이를테면 N이 10인 경우?

그럼 정답 행렬은 이렇게 된다:

귀찮아서 다 안채웠는데, 빈칸은 전부 0이라고 생각하면 된다.

규칙이 보일 것이다.

왼쪽 위에서 오른쪽 아래로 내려가는 대각선에는 짝수들을 순서대로 채워주고

반대 대각선에는 반으로 나눠 한쪽은 전부 1로 채우고 나머지는 전부 0으로 채운다.

자, 그럼 N이 홀수인 경우엔?

N-1의 행렬을 만들어주고

N행 N열에 2×(N-1)를 넣어주면 된다.

이를테면 N=11

정답 소스코드는 나중에 추가 예정.