2021년 정보올림피아드 필기 중등부(16 ~ 20)

2021년도 정보올림피아드 1차대회 필기 중등부 11번부터 15번까지 문제 풀이 입니다.

이전 문제는 아래 링크 확인 바랍니다.

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

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

2024.04.17 - [알고리즘 설명/정보올림피아드 필기] - 2021년 정보올림피아드 필기 중등부(11 ~ 15)

16번

초등부 18번 문제와 같습니다. 아래 링크에서 18번 문제 확인 바랍니다.

https://davincicoding.tistory.com/129#18%EB%B2%88

2021년 정보올림피아드 필기 초등부(16 ~ 20)

 

17번

천사는 6 이상 될 수 없고, 악마는 2 이하가 될 수 없습니다. 먼저 악마가 있을 수 있는 곳 부터 찾아보겠습니다.

거리는 간선의 개수 입니다. 거리를 재는 기준을 정확히 기억하고 있어야 합니다. 먼저 D로부터 3칸 이상 떨어져 있는 모든 위치를 표시하였습니다. 다음으로 A로부터 6이상 떨어져 있는 위치의 표시를 지우면 원하는 결과를 얻을 수 있습니다. 맨 왼쪽부터 거리가 6 이상인 위치를 지워 보겠습니다.

그럼 위와 같은 결과를 얻을 수 있습니다.

 

18번

초등부 19번 문제와 같습니다. 아래 링크에서 18번 문제 확인 바랍니다.

https://davincicoding.tistory.com/129#19%EB%B2%88

2021년 정보올림피아드 필기 초등부(16 ~ 20)

 

19번

단조증가를 만들기 위해서 더하기와 빼기를 적절하게 사용해야 합니다. 앞의 세 개의 수인 3, 10, 8을 단조증가하게 만들기 위해서 가장 쉬운 방법은 3, 10, 10을 만들던가 3, 8, 8을 만들어주면 됩니다. 뒤의 수가 더 작기 때문에 8로 맞추는 것이 더 좋습니다. 3번째부터 5번째까지 수인 8, 4, 11을 단조증가하게 만들기 위해서는 중간의 4를 8까지 증가시켜 주어야 합니다. 이런 방식으로 최대한 적은 연산 횟수를 만들기 위해 숫자들을 조절하면 됩니다.

실제 단조증가 수열의 최소값을 만들기 위해서는 DP로 점화식을 만들 수 있습니다. Slope trick 이라는 알고리즘으로 불리며 상당히 복잡합니다. 아래는 정답 결과의 한 예시 입니다.

 

20번

삼각형을 만들기 위해서는 두 선분이 한 점에서 만나면 됩니다. 즉 이미 사용된 점을 사용하는 순간 상대방이 삼각형을 만들게 됩니다. 이를 방지하기 위해서 사용되지 않은 점들만 사용해 선분을 그리다보면 상대방이 어쩔수 없이 이미 사용된 점을 사용할 것이고, 이를 이용해 삼각형을 만들면 됩니다.

13개의 점이 있기 때문에 모든 점을 겹치지 않게 선분을 이으면 총 6개의 선분을 그릴 수 있습니다. 6개의 선분을 모두 그리면 더이상 사용안된 점으로 선분을 그릴 수 없기 때문에 지게 됩니다. 결국 5번안에 모든 점이 사용되도록 만들면 이기게 됩니다.

연속된 두 점을 잇는 것은 횟수를 줄일 뿐 점들을 줄일 수 없습니다. 한칸 이상 떨어진 두 점을 연결하여 상대방이 6번째 선분을 그릴 수 없게 만들면 됩니다. 아래는 승리한 한 예 중 하나 입니다.