2019년 정보올림피아드 필기 중등부(2 - 4 ~ 2 - 8)

2019년 정보올림피아드 1차 대회 중등부 필기 2-4번부터 2-8번까지 문제 풀이 입니다. 이전 문제는 아래 링크 확인 바랍니다.

2024.03.18 - [알고리즘 설명] - 2019년 정보올림피아드 필기 중등부(1 ~ 5)

2024.03.20 - [알고리즘 설명] - 2019년 정보올림피아드 필기 중등부(6 ~ 10)

2024.03.21 - [알고리즘 설명] - 2019년 정보올림피아드 필기 중등부(11 ~ 2 - 3)

2 - 4번

버튼을 누르면 그 좌 우도 같이 숫자가 변합니다. 모두 0으로 만들기 위해서는 5번째 버튼을 눌러 6번째, 7번째 1을 0으로 바꾸고, 4번째 0은 1로 바뀌게 해야 합니다.

3번째 버튼을 누르면 5번을 누른것과 마찬가지로 3번째, 4번째 1이 0으로 바뀌고 2번째 0만 1로 바뀝니다.

이제 마지막으로 1번째 버튼을 눌러 모두 0으로 바뀌게 합니다.

이렇게 1, 3, 5번 버튼을 누르면 모두 0을 만들 수 있습니다. 이 순서 역시 잘 생각해보면 어떤 순서에 상관없이 동작합을 알 수 있습니다.

 

2 - 5번

먼저 이 문제에서 규칙으로 내세우는 것을 정확히 기억하고 있어야 합니다.

주변에 있다는 것은 가로 세로 거리의 합이 4 이하이다.

탑은 주변에 없고, 나무와 바위는 주변에 있다.

먼저 탑이 주변에 없다는 것을 표현해 보겠습니다. 빨간색으로 되어 있는 부분이 탑이 주변에 있다고 할 수 있는 곳입니다.

거리가 4칸 이하인 부분을 표현 하였습니다. 다음으로 나무와 바위가 주변에 있다고 할 수 있는 부분을 표시 하였습니다. 나무는 노란색, 바위는 파란색이 주변에 있다고 할 수 있는 위치입니다. 그리고 이 두 부분이 겹치는 부분이 초록색 입니다.

따라서 탑이 주변에 없고, 나무와 바위가 주변이 있다고 할 수 있는 답이 되는 부분이 초록색 입니다.

2 - 6번

간단한 DP 문제 입니다. 연속된 날짜로 같은 메뉴를 먹으면 안되기 때문에 그 부분만 조심하면 쉽게 문제를 해결할 수 있습니다. 첫째날에 A를 먹으면 B ~ D중 하나를 먹고, B를 먹으로 A, C, D중 하나를 먹습니다. 이런 식으로 총 4가지의 케이스 중에서 최소값을 계속적으로 고르면 됩니다.

그럼 위와 같이 먹었을 때 최소값을 얻을 수 있습니다. 3번째 날짜에 A 메뉴를 먹지 않고 C 메뉴를 먹는 이유는 연속된 날짜에 같은 메뉴를 먹을 수 없기 때문 입니다.

2 - 7번

게임 이론에 관한 문제 입니다. 님(Nim) 게임과 비슷한 형태로 필승 전략이 존재하는 게임입니다.

제일 왼쪽 아래 칸인 빨간색 칸을 고르면 지기 때문에 죽어 있는 칸을 위와 같이 파란색으로 만들어야 합니다. 그리고 상대방이 1번칸을 선택하면 나는 2번칸을 선택하고, 상대방이 2번칸을 선택하면 나는 1번칸을 선택하여 상대방이 결국 빨간칸을 선택하도록 만드는 것이 핵심 입니다.

잘 생각해보면 저런 모양을 만들기 위해서는 항상 기역자(ㄱ) 모양을 유지해야 합니다.

위 그림의 숫자는 나와 상대방이 둔 순서를 나타낸 것입니다. 파란색은 내가 선택했을 때 죽은 칸이 되는 부분이고, 초록색은 상대방이 선택했을 때 죽은 칸이 되는 부분 입니다.

기역자 모양을 유지하기 위해서는 위 그림과 같이 첫 번째 선택시 1번을 선택 해야 합니다. 상대방이 2번을 선택하면 나는 3번을 선택해서 기역자를 유지합니다. 상대방이 4번을 선택하면 나는 5번을 선택해서 기역자 모양을 유지해야 합니다. 그럼 최종적으로 상대방이 빨간칸을 선택할 수 밖에 없게 됩니다.

2 - 8번

특정한 방향인 오른쪽 위쪽으로는 못가는 것만 주의하면 쉽게 해결할 수 있습니다. 이런 문제는 거꾸로 해결하는 것이 더 쉬울 수 있습니다. 깃발에 도착하기 위해서 어디를 가야하는지 따져봐야 합니다.

깃발의 위치인 G에 도달하기 위해서는 1번에 도달해야 합니다. 1번만이 G에 도달할 수 있기 때문 입니다. 다음으로 1번 위치에 가기 위해서 도달해야 하는 지점을 생각해 보겠습니다.

1번 위치에 도달하기 위해서는 2번 위치에 있어야 합니다. 2번 위치에 도달하기 위해서는 3번 위치에 있어야 합니다. 이런 방식으로 위치를 선택하면 결국 7번 위치에 도달합니다. 7번 위치는 S에서 출발하여 도착할 수 있는 위치 입니다. 이렇게 여러가지 방법으로 문제를 해결할 수 있습니다. 이 방법 뿐만 아니라 다른 방법으로도 8번만에 도달할 수 있다면 정답이 될 수 있습니다.