[BOJ] 10219번 Meats On The Grill

[BOJ] 10219번 Meats On The Grill 문제

구성적(Constructive) 문제가 무엇인지 알아보는 좋은 문제다.

---

PS에서 구성적 문제에서 구성적은 구성적 증명(Constructive proof)에서의 구성적이며, 예시를 들어 문제를 증명하는 방식이다.

구성적 문제의 경우 예시 중 하나만 입력해도 답으로 처리해주기 때문에, 해당 문제에서 정답을 이끌어내는 특정한 방법을 구하는 애드 혹(Ad hoc)의 특성도 보인다.

[Reference article] Constructive 문제를 어떻게 풀 것인가 - 16silver

즉, 이 문제에서만 풀 수 있는 풀이법을 문제를 읽으면서 캐치하는 것이 핵심이라 보면 되겠다.

---

일반적으로 이 문제의 일반적은 해를 구하기 위한 방법으로는 도저히 방법이 나오질 않는다. 당장 문제 예시만 봐도 그럴 것이다.

대신 아무 예시 중 하나만을 보여줘도 된다는 문구가 이 문제의 해결 방안을 보여준다. 이 문구는 "나는 구성적 문제예요!"라고 알려주는 좋은 문구이며, 이 문제에서는 되려 기존에 나온 알고리즘을 생각하는 것이 되려 손해일 가능성이 높아진다.

다시 문제로 가보자. 이 문제는 회전과 대칭을 허용하고 있다. 그리고 고기끼리는 겹쳐지면 안 된다. 마지막으로 아무 예시 중 하나만을 보여줘도 된다. 이 세 가지가 문제에 있음을 꼭 캐치하자.

그렇다면 애드 혹 방식으로 이 문제를 접근해야 하는데, 문제의 조건에서 회전과 대칭을 허용하고 있음에 주목하자.

그 말인즉슨, 180도를 돌린 결과나 y축 대칭으로 뒤집은 결과라 해도 이 문제의 정답이 된다는 뜻이다! 당연히 x축 대칭도 정답이 맞다.

문제의 예제를 우측의 두 방법으로 변형시켜도 답이다

즉, 모든 문제의 예제를 저 둘 중 하나로 구해도 전부 정답이 된다. 왜냐면 문제에서는 회전과 대칭을 허용하고 있고, 저 두 방법은 고기끼리 겹치지도 않으며, 어쨌든 문제의 정답 중 하나이기 때문이다.

---

import sys

if __name__ == '__main__':
    for T in range(int(sys.stdin.readline().rstrip())):
        H, W = map(int, sys.stdin.readline().rstrip().split())
        grill = list()
        for _ in range(H):
            grill.append(sys.stdin.readline().rstrip())
        for now_grill in grill:
            print(now_grill[::-1])

 

본인은 여기서 python으로 구현하기 쉬운 y축 대칭을 선택하였다.

개인적으로 생각하는 것이지만, 구성적 문제의 경우엔 예제 입출력을 보는 게 되려 해害일 가능성이 높다고 생각한다... 오히려 출제진들이 함정을 파서 문제를 더 헷갈리게 만드는 느낌이 든다.