2023 서강대학교 청정수컵 Open Contest

2023 서강대학교 청정수컵 Open Contest

A - 레몬 따기

단순 구현

00:01 AC

 

B - 준석이의 사탕 사기

(전체 사탕 개수) - (홀수 사탕 개수의 최솟값)

00:03 AC

 

C - 동전 복사

(x > 1) + (x < N) + (y > 1) + (y < N)

00:06 AC

 

D - 이민희진

brute force

00:09 AC

 

E - SW 수열 구하기

1, N, 2, (N - 1), 3, ...

00:11 AC

 

J - 유니의 편지 쓰기

누적 합

00:18 AC

 

K - 승형이의 사탕 사기

다음과 같은 점화식을 세울 수 있다.

dp[i][j] = i개의 사탕 상자를 가져 갔을 때 ((사탕의 개수) % K) = j가 되는 사탕의 최대 개수

00:23 AC

 

F - 타노스는 요세푸스가 밉다

지문의 내용을 queue를 이용하여 그대로 구현해주면 된다.

00:27 AC

 

G - 기하가 너무 좋아

세 변의 길이가 동일한 삼각형은 합동이다.

(가장 긴 변의 길이) < (나머지 두 변의 길이의 합)을 만족하는지 확인해주자.

00:39 AC

 

I - 김밥천국의 계단

K번 이내로 N번째 계단에 도달할 수 있는지 확인하면 된다.

필요한 행동 횟수가 K번 미만인 경우 0번째 계단에서 적절한 횟수만큼 지팡이를 두드리면 된다.

 

다음과 같은 점화식을 세울 수 있다.

dp[i] = i번째 계단에 도달하기 위한 최소 행동의 수

구체적으로는 다음과 같이 계산할 수 있다.

int x = i + i / 2;

dp[x] = min(dp[x], dp[i] + 1);

00:42 WA

 

계단 한 칸을 올라가는 경우도 처리해주어야 한다.

다음과 같이 처리할 수 있다.

dp[i] = min(dp[i], dp[i - 1] + 1);

00:44 AC

 

L - K512에서 피자 먹기

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

B[i] = sum(A[1 .. i]) % K

답은 배열 B에서 최빈값의 개수가 된다.

00:49 AC

 

M - PSAT 특별 과정

multi-source bfs

스페셜 저지가 붙어 있으면 굉장히 쉬운 문제가 된다.

사전 순으로 가장 앞서는 문자열을 만드는 것이 난이도를 높인다.

 

이러한 문제는 끝에서부터 탐색하는 전략이 잘 먹힌다.

즉, 종료 문자부터 탐색을 시작하고 시작 문자에서 탐색을 마치면 된다.

각 정점마다 전체 string을 저장하기에는 N 제한이 크다.

그 대신 부모 정점만을 기록하고 부모가 여러 개인 경우 더 작은 문자를 가진 부모를 선택하자.

이러한 문제는 대부분 이렇게 하면 풀린다.

01:07 WA

 

그런데 이 문제에서는 서로 다른 정점에 동일한 문자가 부여될 수 있다.

따라서 부모가 여러 개이고 문자가 동일한 경우에는 사전 순 비교를 적절히 수행할 수 없다.

해결책으로 그냥 모든 부모 정보를 저장하자.

정답이 될 수 있는 정점 후보를 관리하면서 사전 순으로 가장 앞서는 문자열을 만들면 된다.

이때 동일한 정점은 한 번만 고려해야 한다.

01:11 AC

 

H - I Am Knowledge

A[i] <= B[i]인 책부터 우선적으로 읽어도 무방한데 A[i]가 작은 책부터 읽으면 된다.

이제 A[i] > B[i]인 책들만 남게 되는데 이 책들을 읽는 순서는 결정하기가 쉽지 않다.

 

책을 읽는 과정을 거꾸로 생각해보자.

A[i] > B[i]인 책을 읽는 것은 마치 즐거움을 B[i]만큼 소모한 후 다시 A[i]만큼 얻는 것으로 생각할 수 있다.

모든 책을 읽은 후의 즐거움 수치는 쉽게 계산할 수 있고 이 상태에서 B[i]가 작은 책부터 거꾸로 읽어나가면 된다.

01:19 AC

 

끝

끝