[백준] 제3회 숙명여자대학교 프로그래밍 경진대회 (SMUPC) Open Contest 후기
https://www.acmicpc.net/contest/view/1109
제3회 숙명여자대학교 프로그래밍 경진대회 (SMUPC) Open Contest
www.acmicpc.net
[총평]
제1회, 제2회 대회를 겪어보지 못한 터라 어떠한 사전정보 없이 오픈콘을 치게 되었습니다. D번에서 살짝 삽질한 것 빼고는, 나머지 전형적인 문제들을 빠르게 해치워서 나쁘지 않게 본 것 같다는 생각이 드네요. G번을 풀 때 즈음엔 갑자기 다른 대회를 치고 있는 것과 같은 기분이 들었습니다. F번까지는 그래도 '전형적'이라는 기조가 이어지고 있었던 것 같은데, 당황스러울만큼 확 어려워져서.. 이번 대회의 비기로 준비해놓은 것 같은 느낌? 마지막 G번은, 식 전개는 거의 다해놓았는데, 그 식이 행렬 곱셈으로 이어질 수 있다는 것을 몰라서 결국 못 풀었습니다. 사실, 알았어도 빠르게 구현하지 못했을 것 같아서 그닥 아쉽지는..
[문제 풀이]
A번. Welcome to SMUPC!
https://www.acmicpc.net/problem/29699
29699번: Welcome to SMUPC!
화은이는 제3회 SMUPC를 맞이하여 환영의 의미로 "WelcomeToSMUPC"가 반복적으로 적혀 있는 라벨지를 프린트했다. 라벨지에는 공백 없이 글자들이 이어져 있고 "WelcomeToSMUPC"의 마지막 글자인 C 이후에
www.acmicpc.net
문자열이 고정되어 있는 상태에서 $N$번째 글자가 무엇이냐고 묻고 있기 때문에, $N-1$을 문자열의 길이(여기서는 14)로 나눈 나머지값만을 보면 됩니다. ($N-1$을 하는 이유는 $N\geq 1$이기 때문에) 여러가지 방법이 있겠지만, 저는 이 방법이 가장 먼저 떠올랐습니다.
B번. 우당탕탕 영화예매
https://www.acmicpc.net/problem/29700
29700번: 우당탕탕 영화예매
첫째 줄에 영화관 세로줄의 개수 $N$($ 1 \leq N \leq 1\,000$)과 가로줄의 개수 $M$($ 1 \leq M \leq 5\,000$), 영화를 관람할 동아리원의 수 $K$($ 1 \leq K \leq 10$)가 주어진다. 둘째 줄부터 $N$ 개의 줄에 걸쳐 그중
www.acmicpc.net
그저 브루트포스. 어떤 최적화 없이 돌려도 $O(NMK)$가 시간 안에 들어옵니다. 예매한 좌석이 동일하면 같은 경우로 보기 때문에 따로 경우의 수를 나눌 필요도 없습니다. 좌석 $NM$개 각각에서 시작하여 연속하는 $K$개 좌석이 0일 경우 카운트해주면 됩니다. 한편 이런 문제의 경우 항상 인덱스 범위를 조심해야 합니다.
C번. 모스 부호
https://www.acmicpc.net/problem/29701
29701번: 모스 부호
혜민이는 요즘 모스 부호에 관심이 많아졌다. 모스 부호는 짧은 신호와 긴 신호를 적절히 조합하여 문자 기호를 표기하는 방식이다. 각 문자를 나타내는 방식은 미리 정해져 있는데, 예를 들어,
www.acmicpc.net
처음 보고 숨이 턱 막힌 문제. 오픈콘이라 구현했지, 그게 아니었다면..
저난이도의 깡구현은 그냥 뇌 빼고 구현하는 게 가장 좋은 것 같습니다.
D번. 이상한 호텔의 송이
https://www.acmicpc.net/problem/29702
29702번: 이상한 호텔의 송이
송이가 묵고 있는 S 호텔은 $60$층짜리 건물인데, 이 호텔의 구조는 완전 이진 트리의 형태로 나타낼 수 있다. 호텔에 있는 방들을 트리의 노드로, 방과 방 사이를 위아래로 잇는 계단을 간선으로
www.acmicpc.net
처음 봤을 때는 쉽게 안 풀릴 것 같아서 E, F번을 먼저 푼 후 다시 돌아와서 풀었습니다.
방을 거슬러 올라가지 말고, 역으로 1번 방에서 $N$번 방으로 온다고 생각해봅시다. 1번 방에서 내려오면 내려올 수록, 층은 1씩 증가합니다. 또, 내려갈 때 왼쪽으로 가면 현재 호수에 *2-1을 취해야 하고, 오른쪽으로 가면 *2를 취해야 함을 알 수 있습니다.
이러한 규칙과 트리 모양이 완전 이진 트리 모양임을 고려하여 $N$을 이진수로 나타내봅시다. $N = 7$일 때, $111_{(2)}$로 나타낼 수 있습니다. 1번 방에서 7번 방으로 갈 때, 항상 오른쪽으로 내려간다는 점을 미루어 보았을 때, 이진수의 각 자릿수가 1일 때에는 오른쪽으로, 0일 때에는 왼쪽으로 가야 함을 알 수 있습니다. 왜냐하면..
왼쪽으로 내려가면 방 번호가 2배 증가하고, 오른쪽으로 내려가면 방 번호가 2배 증가한 후 1을 더하게 됩니다. 이진수에서 수가 2배 증가한다는 것은 이진수의 오른쪽 끝에 0을 붙이는 것과, 2배 증가한 후 1을 더하는 것은 오른쪽 끝에 1을 붙이는 것과 동치입니다. 따라서 이진수의 각 자릿수 값이 1이면 오른쪽으로 갔다는 것을, 0이면 왼쪽으로 갔다는 것을 의미하게 됩니다. 이때 처음 나오는 1(맨 앞 1)은 1번 방을 의미하는 것이기 때문에, 그 다음 자릿수 값만 봐도 무방합니다.
이상을 종합하여 출력 형식에 맞추어 잘 출력하기만 하면 됩니다.
E번. 펭귄의 하루
https://www.acmicpc.net/problem/29703
29703번: 펭귄의 하루
$1$ × $1$ 크기의 정사각형 칸으로 각각 나누어져 있는 $N$ × $M$의 행렬로 표현되는 펭귄 마을이 있다. 펭귄 마을의 정보는 문자 'S', 'H', 'E', 'D', 'F'로 나타난다. E는 천적이 없어 펭귄이 이동해도 괜
www.acmicpc.net
반드시 물고기들이 서식하는 구역에 들른 후 집에 도착해야 하기 때문에, 각 $NM$개 칸의 상태에 대하여 "물고기들이 서식하는 구역에 들렀는지 안들렀는지를 체크하는 상태"를 추가하여 총 $2NM$개 상태에 따른 BFS를 돌리면 됩니다.
BFS를 많이 연습했다면, 정말 전형적인 문제입니다. 익숙하지 않다면 백준 2206번 - 벽 부수고 이동하기 문제를 풀고 오시는 걸 추천드립니다.
F번. 벼락치기
https://www.acmicpc.net/problem/29704
29704번: 벼락치기
숙명여자대학교의 알고리즘 학회 ALGOS에 합격한 혜민이는 너무 기뻐 마음이 들뜬 나머지 프로그래밍 과제가 있는 것을 잊어버리고 말았다. 프로그래밍 과제로는 다양한 난이도의 문제 $N$개가
www.acmicpc.net
최소한의 벌금을 내려면, 해결한 문제의 벌금 총 합이 최대이면 됩니다. 따라서 다음과 같이 dp식을 정의해볼 수 있습니다.
- dp[i][j] : 총 기간이 j일이고, i번째 문제까지를 살펴보았을 때, 해결한 문제의 벌금 총합의 최댓값.
dp식 정의에 따라 dp식은 다음과 같이 전개해볼 수 있습니다.
- $day[i]$는 $i$번째 문제를 해결하는 데 소요되는 일수를, $money[i]$는 $i$번째 문제를 해결하지 못했을 때 제출해야 하는 벌금을 나타냄.
- $dp[i][j] = \mathrm{max}(dp[i-1][j], dp[i-1][j-day[i]] + money[i])$
물론 $\mathrm{max}$의 뒤 항은 $j-day[i] \geq 0$일 때만 가능합니다. 만약 뒤 항 조건을 만족하지 못한다면, 그냥 $dp[i-1][j]$ 값을 대입하면 됩니다.
복잡하게 설명한 것 같지만, 그냥 전형적인 배낭 문제(Knapsack)의 변형일 뿐입니다.
[업솔빙]
(추후 추가 예정)