강원도 대학생 코딩 경진대회 Part 2 - 문제 풀이

대회 종료 후 스코어보드

서론

운영진 측에 스코어보드 공개 또는 제가 제출한 코드의 제출 시각 및 채점 결과 공개를 요청하였습니다.

메일은 바로 읽으셨는데 며칠이 지나도록 답변이 없네요.

때문에 이번 후기는 AC 시각만 기재합니다.

그리고 이번 대회는 공식 에디토리얼이 제공되지 않는 것 같아서 평소보다는 꼼꼼하게 풀이를 작성하였습니다.

상대적으로 꼼꼼하다는 것이지 완벽하게 작성하였다는 말은 아닙니다.

 

대회 시작 시각 지연

대회 직전에 있었던 강연이 늦게 끝나서 대회 시작 시각이 5분 지연되었습니다.

거기에 제가 있었던 실습실의 감독관이 시간을 제대로 확인하지 않아 30초 정도 추가 지연이 있었습니다.

 

A - 선물

단순 구현

00:07 AC

 

B - 운명

(i번 색 왼쪽 양말과 같이 신을 수 있는 오른쪽 양말의 개수) = X - (i번 색 오른쪽 양말의 개수)

00:10 AC

 

이후 C번을 보니 단순한 bfs 문제였고 금방 코딩하였으나 의문의 WA를 받았다.

아무리 봐도 잘못된 부분이 보이지 않아서 멘탈이 흔들렸다.

결국 C번을 던지고 D번을 잡았는데 이마저도 RTE를 받았다.

그 사이 jyheo98님이 C번 퍼솔을 가져가셨다.

말 그대로 주도권도 다 뺏기고 허둥거리는 상황이었다.

 

C - 해킹

단순한 multi-source bfs 문제이다.

보안 시스템이 설치된 컴퓨터에서 bfs를 수행하면 각 컴퓨터에 보안 시스템이 설치되는 시점을 알 수 있다.

이를 이용하면 각 컴퓨터를 해킹하였을 때 얻을 수 있는 금액도 구할 수 있다.

금액이 높은 컴퓨터부터 그리디하게 해킹하면 된다.

보안 시스템이 설치되지 않은 컴퓨터가 있다면 -1을 출력하면 된다.

 

여기서 작은 함정이 있다.

i번 컴퓨터에 보안 시스템이 설치되지 않았더라도 A[i]가 0이라면 답은 -1이 아니다.

이 코너 케이스 때문에 많은 참가자들이 울부짖었다.

00:35 AC

 

D - 스터디 카페

이 문제를 풀기 위해서는 누적 합(imos법)과 좌표 압축 기법에 대하여 알고 있어야 한다.

잘 모르겠다면 이것부터 공부하고 오자.

 

다음과 같은 배열 C를 정의하자.

C[i] = i일의 스터디 카페 이용자 수

가장 단순한 방법은 M개의 이용 기록에 대하여 C[S[i]]부터 C[E[i]]까지 1을 더해주는 것이다.

이보다 더 효율적인 방법이 있는데 C[S[i]]에 1을 더하고 C[E[i] + 1]에서 1을 빼주자.

그리고 배열 C의 누적 합을 구하면 위와 동일한 결과를 얻을 수 있다.

예제 입력 1의 경우 다음과 같은 결과를 얻는다.

C = [0, 0, 1, 1, 1, 2, 2, 1, 0, ...]

 

다음과 같은 배열 D를 정의하자.

D[i] = 이용자 수가 i명인 날의 수

이는 단순히 배열 C의 빈도수를 구하는 것과 같다.

이때 D[0]은 필요하지 않으므로 0은 무시해도 된다.

예제 입력 1의 경우 다음과 같은 결과를 얻는다.

D = [0, 4, 2, 0, ...]

 

이제 최소 수익을 구할 것인데 먼저 배열 A를 정렬해주자.

이용자 수가 i명일 때의 수익을 최소화하려면 배열 A의 가장 앞에 있는 i개의 값을 선택하면 된다.

이는 sum(A[0 .. (i - 1)])과 같은데 위에서와 마찬가지로 누적 합 배열을 만들면 빠르게 구할 수 있다.

최대 수익 또한 유사한 방법으로 구할 수 있다.

배열 A를 뒤집은 배열 R을 만든 후 누적 합을 구해주면 된다.

 

하지만 S와 E 제한이 크기 때문에 위와 같은 풀이는 불가능하다.

여기서 좌표 압축이 필요해진다.

S[i]와 (E[i] + 1)에 대하여 좌표 압축을 수행하면 다음과 같은 결과를 얻는다.

편의를 위하여 0을 추가하였다.

[0, 2, 5, 7, 8] -> [0, 1, 2, 3, 4]

 

예제 입력 1의 경우 배열 C는 다음과 같아진다.

C = [0, 1, 2, 1, 0]

이제 배열 D를 구해야 하는데 이전과 같이 단순히 빈도수를 구하면 잘못된 결과를 얻는다.

현재 배열 C는 좌표 압축된 인덱스로부터 얻은 결과이므로 (다음 좌표) - (현재 좌표)만큼을 더해주어야 한다.

예제 입력 1의 경우 다음과 같이 계산할 수 있다.

D[1] = (5 - 2) + (8 - 7) = 4

D[2] = 7 - 5 = 2

 

나머지는 기존 풀이와 동일하다.

본 대회에서는 컴파일러가 제공되지 않아서 예제가 나오지 않는 코드를 작성하였다.

다행히 사소한 구현 실수여서 금방 고치고 AC를 받았다.

00:39 AC

 

E - 육각형 순회

종이와 펜이 없어서 조금 힘들었다.

먼저 (1, 1)에서 시작하는 hamiltonian cycle을 구해보자.

방법은 많겠지만 나의 방법은 다음과 같다.

 

(1, 1)에서 시작해서 한 행씩 차례대로 지그재그 모양으로 내려오자.

이렇게 (2 * N - 3, 2 * N - 1)까지 이동하는데 이때 첫 번째 열은 방문하지 않고 남겨두어야 한다.

마지막 두 행은 시험지에 비가 내리는 듯한 사선 모양으로 이동해주자.

(2 * N - 1, 1)까지 이동하면 첫 번째 열만 남게 되는데 첫 번째 열을 타고 (1, 1)로 돌아오면 된다.

 

말로만 설명하면 이해가 어려울 수 있으니 예시를 가져왔다.

N = 2인 경우, DCZQZQE

N = 3인 경우, DDCAAZDDDZZQZQZQQEE

N = 4인 경우, DDDCAAAZDDDDCAAAAACDDDDZZQZQZQZQQQEEE

...

규칙은 어렵지 않으니 잘 코딩해주자.

 

이제 임의의 정점에서 시작하는 hamiltonian cycle을 구해보자.

hamiltonian cycle은 모든 정점을 단 한 번 방문한 후 시작 정점으로 돌아오는 cycle이다.

때문에 위에서 구한 문자열을 적절히 rotate시키면 끝이다.

얼마만큼 rotate해야 하는지는 case work로 처리해주면 된다.

 

나는 다음과 같이 4개의 case로 나누어서 처리해주었다.

• 첫 번째 행인 경우
• 첫 번째 열인 경우
• 마지막 두 개의 행인 경우
• 그 외의 경우

사소한 구현 실수가 있어서 WA를 2번 받았다.

01:26 AC

 

끝

끝