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

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

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

16번

초등부 19번과 같습니다. 아래 링크를 통해 19번 확인 바랍니다.

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

2023년 정보올림피아드 1차대회 초등부 필기 16번부터 20번까지 문제 풀이 입니다. 1번부터 15번은 아래 링크 확인 바랍니다. 2024.04.07 - [알고리즘 설명/정보올림피아드 필기] - 2023년 정보올림피아

davincicoding.co.kr

최단 거리를 51로 만들기 쉽지 않습니다. 최대한 돌아가야 길이가 늘어나는데 가로, 세로 모두 홀수라 일자로 늘리면 원하는 모양이 나오지 않습니다. 길이를 맞추기 위해 중간중간 길이를 늘려야 51 이상의 거리를 만들 수 있습니다. 대각선 아래는 정답의 예 입니다.

초등부 20번과 같은 문제 입니다. 아래 링크를 통해 20번 확인 바랍니다.

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

davincicoding.co.kr

어느쪽으로 교환을 하는 것이 좋을지 따져보며 문제를 해결합니다. 여러번 테스트를 해가며 횟수를 줄이는 문제로 따로 겹치는 번호 때문에 인접하게 만들기 힘들다면 과감히 한쪽으로 몰아주는 것이 더 빠릅니다. 교환 횟수가 맞다면 모양은 아래와 같지 않아도 됩니다.

A에서 B로 가는 간선이 있고, B에서 C로 가는 간선이 있어야 합니다. 이런 형태의 간선이 가장 많은 경우를 만들어야 하는 문제 입니다.

따라서 모든 간선들을 두 개씩 연결된다는 생각으로 만들어주어야 합니다. 그래야 한 간선이 AB가 되고, 이어진 다른 간선이 BC가 될 수 있습니다.

정점에 연결된 간선이 짝수라면 반은 들어오고, 반은 나가는 형태로 만들어 줍니다. 연결된 간선이 홀수라면 나가는 간선을 하나 더 만들어 준다는 생각으로 그래프를 구성하면 됩니다. 아래는 정답중 하나의 케이스 입니다.