[writeup]천하제일 코딩대회(선린) 1회 - 예선 문제 풀이
ひさしぶり
오늘은 며칠 전에 학교에서 진행된 코딩 대회 문제 풀이를 해보려고 합니다. 저는 사실 실제로 대회장에서는 A 문제 밖에 못 풀었지만 끝나고 나서 제 자신에게 좀 화가 나서 주말동안에 풀었는데, 다 풀었습니다!!
그래서 이 기쁨을 좀 나누고 싶어서 이 글을 씁니다.
Link: ICPC.ME
#No.1(A) 와이버스 부릉부릉
Question
버스 운전수 비와이 씨가 운전하는 버스(verse아님 ㅎ)는 N개의 정거장을 거친 후 종착역에 도착한다. 각 정거장은 내릴 인원수와 올라탈 인원수가 정해져 있다. 종착역에 도착하면 버스에 타고 있던 모든 사람이 내린다.
Input
첫 줄에 출발역과 종착역을 제외한 정거장의 수 N(1<=N<=100,000)과 출발역에서 탑승하는 사람의 수 K(1<=K<=10,000)가 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 i번째 정거장에서 탑승하는 인원 A와 하차하는 인원 B가 주어진다. (0<=A,B<=10,000)
Output
종착역에 도착했을 때, 버스 운전수의 이름을 출력해라.
Example Input
3 2
10 3
21 8
0 15
Example Output
비와이
처음에 이 문제를 보고 “아… 뭐지?? 분명히 기사는 한 명 밖에 없는데..?” 이런 생각이 들었다. 그래서 별 짓을 다 했는데 알고 보니 그냥 출력하면 됐었다 ㅋㅋㅋ
A.c
#include <stdio.h>
int main(void)
{
puts('비와이');
}#No.2(B) 욱제는 결정장애야!!
Question
욱제는 매일 세계사에 한 획을 그을만한 심각한 비결정론적 문제에 직면한다. 그렇다. 바로 저녁메뉴를 고르는 것이다.
매일 반복되는 중대한 선택에 지친 욱제는 N일 동안의 저녁메뉴를 미리 골라두기로 했다. 하지만 결정장애가 있는 욱제는 메뉴를 스스로 고르는 일에 큰 어려움을 느꼈다. 그래서 2N개의 공과 N개의 메뉴를 준비한 뒤 2개의 공에 같은 메뉴를 적고, 이미 번호가 적힌 공과 번호가 겹치지 않도록 공에 1~2N까지의 번호를 임의로 부여했다. 따라서 2N개의 공들은 1~2N까지 모두 다른 번호를 부여받게 된다.
욱제는 N일의 메뉴를 모두 정할 때까지 공을 번호 순서대로 확인한다. 공을 뽑았을 때 바구니에 같은 메뉴의 공이 이미 들어있다면, 뽑은 공과 이미 들어있는 공을 버린 뒤, 그 공에 적힌 메뉴로 저녁 메뉴를 순서대로 채워나간다. 같은 메뉴의 공이 들어있지 않다면, 바구니에 공을 넣고 계속 공을 뽑아나간다.
하지만 슬프게도 결정장애 말기 판정을 받은 욱제는 바구니의 크기마저도 스스로 고를 수가 없었다. 욱제를 도와주자! 욱제가 주어진 순서대로 공을 뽑았을 때, 바구니에는 최대 몇 개의 공이 동시에 존재할 수 있을까?
Input
첫째 줄에 공의 개수 N이 주어진다. (1 <= N <= 100,000) 둘째 줄에 공의 번호 순서대로 해당하는 공에 적힌 메뉴가 주어진다. 편의상 메뉴는 1부터 N까지의 자연수로 표현되어 주어진다. (1 <= 메뉴 <= N)
Output
주어진 순서대로 공을 뽑았을 때, 바구니에 동시에 존재할 수 있는 공의 최대 갯수를 출력한다.
Example Input
3
1 3 3 2 1 2
Example Output
2
Example Input2
5
1 1 2 2 3 3 4 4 5 5
Example Output2
1
뭐… 처음에 이 문제를 봤을 때 “이 XX는 뭐지?” 하고 문제를 접근했다. 문제를 풀려면 우선 국어를 잘 해야한다. 문제 이해를 하는 데 좀 걸렸는데 결국 문제를 머리 속에 있는 것을 코드로 옮기는 것이였다.
시험장에서는 왜 boolean을 생각하지 못 했을까 하는 후회가 남지만 말이다.
이 문제는 키 포인트는 1 과 0이라는 것이다. 배열을 만들어 놓고 2N만큼 반복을 하면서 숫자를 하나씩 받고 배열 arr[k]에 값이 기존에 있는 지 없는 지 확인하면서 카운트 증가 or 감소 해주면 된다.
그리고 결국에는 바구니 안에는 공은 없다.
생각보다 굉장히 간단하다.
B.c
#include <stdio.h>
#include <stdbool.h> // boolean을 사용하기 위한 헤더파일
int max(int a, int b) { return a > b ? a : b; }
int n, cnt, k, ans;
bool check[100001]; // bool 변수
//n은 공의 개수, cnt는 존재가능최대개수, k는 반복문 돌면서 받을 값
int main(void)
{
scanf("%d", &n);
for (int i = 0; i < 2 * n; ++i)
{
scanf("%d", &k);
check[k] ? --cnt : ++cnt; // check[k]가 true면 감소, false면 증가가 되는 거다.
check[k] ^= 1; // ^연산자는 같으면 0, 같지 않으면 1 이다.
ans = max(ans, cnt);
}
printf("%d", ans);
return 0;
}#No.3(C) 준오는 조류혐오야!!
Question
심술쟁이 해커 임준오(동탄 주민)는 새를 싫어한다. 특히 비둘기를 싫어한다.
준오는 수업시간에 옆자리 짝꿍과 빙고게임을 하기로 했다. 준오와 짝꿍은 각자 원하는 숫자를 n*m 격자의 빙고판에 적었다. 그러고는 서로의 빙고판을 교환했는데, 준오는 짝꿍의 빙고판을 확인하자마자 화가 치밀어 올랐다. 짝꿍의 빙고판에 9가 들어간 숫자들이 엄청 많아서 비둘기가 떠올랐기 때문이다. 그래서 준오는 짝꿍의 빙고판을 부숴버렸다.
하지만 준오의 폭동에는 특별한 룰이 있다. 바로 모든 행과 열을 통틀어서 9가 가장 많이 쓰여 있는 행 또는 열을 단 하나만 부수는 것이다!
빙고판을 부수는 순간 준오와 선생님의 눈이 마주쳤고, 선생님은 빙고판에 남아있는 9의 개수만큼 준오를 때리기로 했다. 준오는 몇 대를 맞아야할까?
Input
첫째 줄에 직사각형 빙고판의 크기를 뜻하는 n(1≤n≤500)과 m(1≤m≤500)이 주어진다. 다음 줄부터 n개의 줄에 걸쳐 각 줄마다 m개의 숫자들이 주어진다. 이는 크기가 n*m인 짝꿍의 빙고판의 상태를 나타내며, 빙고판에는 10,000 이하의 자연수들이 적힌다.
Output
준오가 몇 대 맞아야 하는지 출력한다.
Example Input
3 4
1 2 3 9
4 5 9 6
9 7 8 9
Example Output
2
Example Input2
4 4
11 12 19 14
99 39 14 90
13 47 81 99
32 72 29 66
Example Output2
4
Hint
첫 번째 예제에서, 3행 또는 4열을 부수면 2개의 9가 남고 준오는 총 2대를 맞는다.
두 번째 예제에서, 2행을 부수면 19, 99, 29가 남고 준오는 총 4대를 맞는다.
이 문제는 꽤나 쉬웠는데 나는 못 했따 ㅋㅋㅋㅋ
우선, 잡아야 할 함수는 문제를 보면 알 수 있듯이 배열로 받은 숫자들을 9가 몇개 있는 지 알아내야 하는 거다.
그리고 가로, 세로에 9가 몇 개 있는지 확인 해서 최대로 가지고 있는 줄의 9의 개수를 전체 9의 개수에서 지우는 작업으로 했다.
코드를 보자
C.c
#include <stdio.h>
int arr[500][500];
int ans1, ans2;
int f(int a) {
int cnt = 0;
while (a > 0)
{
if (a % 10 == 9) ++cnt;
a /= 10;
}
return cnt;
}
int max(int a, int b) { return a >= b ? a : b; }
int main(void)
{
int n, m, i, j;
int tot= 0, fin = 0;
scanf("%d %d", &n, &m);
for (i = 0; i < n; ++i) for (j = 0; j < m; ++j)
scanf("%d", &arr[i][j]);
//세로 최댓값
for (i = 0; i < m; ++i) {
tot = 0;
for (j = 0; j < n; ++j) {
tot += f(arr[j][i]);
}
ans1 = max(ans1, tot);
}
//가로 최댓값
for (i = 0; i < n; ++i) {
tot = 0;
for (j = 0; j < m; ++j) {
tot += f(arr[i][j]);
}
ans2 = max(ans2, tot);
}
fin = max(ans1, ans2);
tot = 0;
for (i = 0; i < n; ++i)
for (j = 0; j < m; ++j)
tot += f(arr[i][j]);
printf("%d\n", tot - fin);
return 0;
}#No.4(D) 쿼리 맛보기
Question
어떤 문제에 비슷한 형태의 질문이 여러 개 주어지는 문제를 쿼리 문제라고 부른다. 쿼리 문제는 쿼리가 주어진 순서대로 실행해서 해결할 수도 있지만, 그것이 불가능하거나 조건이 맞는 경우에는 쿼리의 순서를 임의로 바꿔서 더 편하게 해결할 수도 있다. 우리는 예선 문제에 쿼리에 대한 설명이 등장했기 때문에 본선 문제에 쿼리 문제가 나올 것이라는 예상을 쉽게 해볼 수 있다.
이 문제에서는 길이 n의 수열과 q개의 쿼리가 주어진다. 주어지는 쿼리의 종류는 다음과 같다.
1 a b : [a, b] 구간의 합을 구해서 출력하고, a번째 숫자와 b번째 숫자를 서로 스왑(swap) 한다.
2 a b c d : [a, b] 구간의 합에서 [c, d] 구간의 합을 뺀 값을 출력한다.
[a, b] 구간의 합이란, 수열의 a~b번째 숫자를 모두 더한 값을 의미한다. 모든 구간의 합과 쿼리의 출력값이 항상 int형의 범위를 넘지 않음이 보장된다.
Input
첫째 줄에 수열의 길이를 뜻하는 n(1≤n≤1,000)과 쿼리의 개수를 뜻하는 q(1≤q≤10,000)가 주어진다. 둘째 줄에 길이 n의 수열이 하나의 공백을 사이에 두고 주어진다. 수열의 각 숫자들은 모두 int형 범위 이내이다. 이후 셋째 줄 부터 q개의 줄에 걸쳐 쿼리가 주어진다. 쿼리의 형식은 “1 a b” 또는 “2 a b c d”이다. a, b, c, d는 n보다 작거나 같은 자연수이며, a≤b, c≤d임이 보장된다.
Output
주어진 쿼리의 출력값을 q개의 줄에 걸쳐 출력한다.
Example Input
5 2
3 5 -2 3 -12
2 1 3 2 4
1 2 5
Example Output
0
-6
Example Input2
7 3
12 5 -1 0 -4 3 -10
1 2 7
2 1 4 2 3
2 1 7 3 4
Example Output2
-7
12
6
description 그대로 코드로 작성하면 되는 재미있는 문제다.
쿼리문 첫 번째 숫자를 판별해서 1일때는 더해주고 swap 해주면 되고 2일 때는 a - b 더하고 c - d 더해서 그 두 값을 빼주면 된다.
이 작업을 q번 반복해주면 끝!
D.c
#include <stdio.h>
int n, qry, arr[1001];
int k, s1, s2;
int main(void)
{
int tmp;
scanf("%d %d", &n, &qry);
for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
for (int j = 0; j < qry; ++j) {
int a, b, c, d, s1 = 0, s2 = 0;
scanf("%d", &k);
if (k == 1) {
scanf("%d %d", &a, &b);
for (int i = a; i <= b; ++i) s1 += arr[i];
printf("%d\n", s1);
// swapping
tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
else {
scanf("%d %d %d %d", &a, &b, &c, &d);
for (int i = a; i <= b; ++i) s1 += arr[i]; for (int i = c; i <= d; ++i) s2 += arr[i];
printf("%d\n", s1 - s2);
}
}
return 0;
}#No.5(E) 문홍안
Question
대한 마을의 계곡에는 100개의 돌이 일렬로 놓인 징검다리가 있다. 원래 징검다리의 돌들은 평범한 돌이었지만 마을의 무속인 최손실 씨의 저주에 걸려 특별한 성질을 띠게 되었다. 그것은 바로 한 번 밟을 때마다 돌의 색깔이 바뀐다는 것이다. 돌은 파란색, 빨간색, 초록색 중 하나의 색깔을 가지며 파란색일 때 밟으면 빨간색, 빨간색일 때 밟으면 초록색, 초록색일 때 밟으면 다시 파란색으로 바뀐다. 편의상 돌의 번호를 징검다리의 왼쪽부터 1번이라고 하자.
대한 마을에 사는 김그네 씨에게는 세 명의 아들이 있다. 첫째 아들 문주인 씨는 파란색을 좋아한다. 둘째 아들 홍지표 씨는 빨간색을 좋아한다. 셋째 아들 안청소 씨는 초록색을 좋아한다.
김그네 씨는 재산을 세 명에게 어떻게 분배할지 고민이 되었지만, 강에 있는 그 징검다리를 떠올리고 좋은 방법을 생각해냈다. 다음 날, 김그네 씨는 N명의 비서들을 징검다리 돌에 임의로 배치시켰다. 그러고는 모두 왼쪽 또는 오른쪽을 바라보고 서도록 했다. 비서들이 처음 돌 위에 올라섰을 때의 모든 돌의 색깔은 파란색이다.
김그네 씨가 “시작!”을 외치는 순간 N명의 비서들은 모두 자신이 바라보는 방향으로 1초마다 한 번씩 다음 돌로 건너간다. 징검다리의 돌은 충분히 넓기 때문에, 여러 명이 한 돌을 동시에 지나갈 수 있다.
김그네 씨는 모든 비서들이 징검다리를 건넜을 때, 최종적으로 남아있는 색깔별 돌들의 개수에 비례해서 재산을 물려주려고 한다. 이를테면 색깔별 돌의 개수를 각각 a, b, c라고 할 때, 재산을 a;b:c로 배분해서 나눠주는 것이다. 김그네 씨의 아들들은 재산을 얼마나 물려받을 수 있을까?
Input
첫째 줄에는 김그네 씨의 재산을 나타내는 정수 P(0 <= P <= 290,000)가 주어진다. 둘째 줄에는 비서의 수 N(0 <= N <= 100)이 주어진다. 그 다음 줄부터 N개의 줄에 걸쳐 각 비서의 위치와 방향이 공백을 사이에 두고 주어진다. 위치는 돌의 번호로 주어지며, 방향은 ‘L’이면 왼쪽, ‘R’이면 오른쪽을 의미한다. 처음의 비서들이 같은 돌 위에서 출발하는 입력은 없다.
Output
세 줄에 걸쳐서 문주인, 홍지표, 안청소 씨 순서대로 물려받을 재산을 소수점 둘째 자리까지 출력한다.
Example Input
100000
3
60 R
25 L
50 R
Example Output
26000.00
34000.00
40000.00
벌써 5번째, 마지막 문제다!!
이 문제를 접근할 때 고려해야 하는 점은 몇 번 밟았는 지에 따라서 색깔이 바뀌는 것을 생각해야 한다.
만약 cnt가 있으면 cnt mod(%) 3을 했을 때 0 이라면 파랑색, 1이면 빨강색, 2이면 초록색이라는 것이다.
이것은 문제 힌트에도 나와있는 것이다.
그렇다면 코드를 작성하기 전에 어떻게 짜야할 지 생각 해 보자.
크기가 100인 정수형 배열을 하나 만들어 두자.
direction과 position이 주어지면 그 위치를 시작으로 for문을 돌면 된다. for을 돌 때 if문을 이용해 R과 L을 구분해서 for문을 돌면 될 것이다.
그 다음에 blue, red, green 의 비율을 알아야하기 때문에 배열을 만들어 주고 1~100번까지 다 돌면서 cnt % 3을 한다. 그리고 값들을 blue, red, green을 담고 있는 변수들에다가 넣어주면 된다.
마지막으로 실수형으로 출력 해줘야하기 때문에 돈 * 0.01 * 색깔 수. 이렇게 출력해주면 됩니다.
뭔가 설명이 부족한데… 이해가 잘 안 되신다면 댓글 or qkrehddus01@gmail.com 으로 남겨 주시길 바랍니다. 성심성의껏 답변해 드리겠습니다.
코드를 보시면 이해가 잘 될 겁니다. 사실 이 문제가 배점은 높은데 어느정도 재미있기도 하고 ㅋㅋㅋㅋ (문홍안이라니) 잘 풀리기 때문에 이 문제는 한 번 꼭 해보시길 바랍니다.
E.c
#include <stdio.h>
int arr[101];
double color[3];
int main(void)
{
int p, n;
int way;
char pos;
scanf("%d", &p);
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d %c", &way, &pos);
if (pos == 'R') {
for (int j = way + 1; j <= 100; ++j)
++arr[j];
}
else {
for (int j = 1; j <= way - 1; ++j)
++arr[j];
}
}
for (int i = 1; i <= 100; ++i) color[arr[i] % 3]++;
for (int i = 0; i < 3; ++i) printf("%.2lf\n", 0.01 * p * color[i]);
return 0;
}<끝>