2023 서강대학교 청정수컵 Open Contest
2023 서강대학교 청정수컵 Open Contest
www.acmicpc.net
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
끝
끝