대회 정보와 문제 리스트: https://www.acmicpc.net/contest/view/242
문제 검수에 많은 도움 주신 sgc109, joonas, baactree님 감사드립니다!
A. 걷다보니 신천역 삼 (Small)
풀이
n 제한이 굉장히 작기 때문에 모든 경우의 수를 전체 탐색 해보면 된다.
코드
#include <stdio.h>
#include <math.h>
int n, cnt;
void gogo(int len, int num) {
if (len == n) {
if (num % 3 == 0 && num != 0) cnt++;
return;
}
for (int i = 0; i < 3; i++) {
if (i == 0 && len + 1 == n) continue;
gogo(len + 1, num + i * pow(10, len));
}
}
int main() {
scanf("%d", &n);
gogo(0, 0);
printf("%d", cnt);
return 0;
}
B. 걷다보니 신천역 삼 (Large)
풀이
이전 Small 문제와 다른 점은 n 제한이 크다는 것이다.
dp[i][j] = 자릿수 i인 숫자를 3으로 나눈 나머지가 j인 경우의 수 라고 두자.
dp[i][j] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]로 정의할 수 있다.
dp[i][0]을 예로 들어보자.
dp[i-1][0]에 숫자 0, dp[i-1][1]에 숫자 2, dp[i-1][2]에 숫자 1을 더하면
위의 셋 모두 dp[i][0]이 된다.
이는 모든 j에 대해 마찬가지이다.
점화식을 조금 더 정리하면 2*3^(n-2)라는 식을 이끌어 낼 수 있다.
n = 1인 경우를 제외하고, 초깃값 2를 시작으로 자릿수가 하나 증가할 때마다 답이 3배씩 증가한다.
dp 배열을 사용해도 좋고, 위의 수식을 사용해도 좋다.
코드
#include <stdio.h>
const int n_ = 33333 + 3;
const int mod = 1e9 + 9;
int n, dp[n_][3];
int main() {
scanf("%d", &n);
dp[0][0] = dp[1][0] = dp[1][1] = dp[1][2] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 3; j++) for (int k = 0; k < 3; k++)
dp[i][j] = ((long long)dp[i][j] + dp[i - 1][k]) % mod;
}
long long ans = (dp[n][0] - dp[n - 1][0] + mod) % mod;
printf("%lld", ans);
return 0;
}
#include <stdio.h>
const int mod = 1e9 + 9;
int n; long long a;
int main() {
scanf("%d", &n);
if (n > 1) a = 2;
while (n-- > 2) a = a * 3 % mod;
printf("%lld", a);
}
C. 나는 행복합니다~
풀이
좌석의 번호는 n에 상관 없이 m에만 영향을 받는다.
좌석의 세로 좌표는 k / m이고, 가로 좌표는 k % m이다.
코드
#include <stdio.h>
int main() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
printf("%d %d", k / m, k % m);
return 0;
}
D. 너의 이름은
풀이
메세지를 읽었는지 확실히 알 수 있는 사람은
무조건 메세지를 읽은 A와,
q번째 메세지를 보낼 때 읽은 사람 수가 같은 사람들과,
q번째 메세지 이후로 메세지를 보낸 사람들이다.
실제 카카오톡 채팅방을 떠올리면 풀기 수월하다.
코드
#include <stdio.h>
const int k_ = 1e4 + 1;
int n, k, q, num[k_], who[k_];
bool chk[26];
int main() {
scanf("%d %d %d", &n, &k, &q);
for (int i = 1; i <= k; i++) {
int a; char c;
scanf("%d %c", &a, &c);
num[i] = a, who[i] = c - 'A';
}
if (!num[q]) return ~printf("-1");
for (int i = 1; i <= k; i++)
if (num[i] >= num[q]) chk[who[i]] = 1;
chk[0] = 1;
for (int i = 0; i < n; i++)
if (!chk[i]) printf("%c ", i + 'A');
return 0;
}
E. 스테판 쿼리
풀이
각 라운드마다 양 측이 낸 가위바위보의 종류(?)가 주어진다.
문제에서 주어진 조건에 맞게 최대 연승 횟수를 구하면 된다.
코드
#include <stdio.h>
int n, win, cnt, ans, a[333], b[333];
int max(int a, int b) { return a > b ? a : b; }
int res(int a, int b) {
if (a % 3 == (b + 1) % 3) return -1;
if (b % 3 == (a + 1) % 3) return 1;
return 0;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) scanf("%d", &b[i]);
for (int i = 0; i < n; i++) {
int ret = res(a[i], b[i]);
if (!ret) ret = win * -1;
win == ret ? cnt++ : (cnt = 1, win = ret);
ans = max(ans, cnt);
}
printf("%d", ans);
return 0;
}
F. 욱제는 도박쟁이야!!
풀이
양쪽 끝의 동전을 하나 또는 두 개만 뒤집는 것이 가능하고, 뒤집는 횟수에 제한이 없기 때문에
처음부터 하나씩 원하는 방향으로 뒤집어 나가면 모든 동전을 원하는 방향으로 뒤집을 수 있다.
(동전의 합의 최댓값) - (동전의 합의 최솟값)은 각각 동전의 절댓값의 합에 부호를 붙인 값과 같으므로
출력해야 하는 값은 (동전의 절댓값의 합) + (동전의 절댓값의 합)이 된다.
코드
#include <bits/stdc++.h>
int main() {
int n, a, sum = 0;
scanf("%d", &n);
while (n--) scanf("%d", &a), sum += abs(a);
printf("%d", sum * 2);
return 0;
}
G. 조교는 새디스트야!!
풀이
학생들을 번호 순서대로 정렬 했을 때, 원래 서있던 순서와 다른 학생들의 수를 구하면 된다.
코드
#include <stdio.h>
int n, num, i, cnt;
int main() {
scanf("%d", &n);
for (i = 1; i <= n; i++) scanf("%d", &num), num != i ? cnt++ : 1;
printf("%d", cnt);
}
H. 준오는 최종인재야!!
풀이
영중이의 문제 풀이 시스템은 노드 n개가 n-1개의 간선으로 연결된 트리 구조임을 알 수 있다.
가장 많은 문제를 푼다는 건, 트리에서 가장 많은 노드를 지난다는(깊이가 가장 깊다는, 지름이라는) 것이다.
최소한의 시간이라는 건, 간선의 가중치의 합이 가장 작다는 것이다.
따라서 깊이가 가장 깊고, 간선의 가중치의 합이 가장 작은 경로를 찾으면 된다.
다르게 얘기하자면, 모든 간선의 가중치를 1이라 가정하고 지름을 구하는 과정에서
나올 수 있는 모든 지름 중에서, 원래 가중치의 합이 가장 작은 지름을 구하면 된다.
이를 간단한 탐색으로 구현할 수 있다.
코드
#include <bits/stdc++.h>
#define fst first
#define snd second
using namespace std;
int n, t;
vector<pair<int, int> > gph[50005];
pair<pair<int, int>, int> dfs(int now, int par, int dph) {
pair<pair<int, int>, int> ret = { { dph,0 },now };
for (int i = 0; i < gph[now].size(); i++) {
int nxt = gph[now][i].fst;
int dst = gph[now][i].snd;
if (nxt == par) continue;
auto tmp = dfs(nxt, now, dph + 1);
tmp.fst.snd -= dst;
ret = max(ret, tmp);
}
return ret;
}
int main() {
scanf("%d%d", &n, &t);
for (int i = 0; i < n - 1; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
gph[u].push_back({ v,w });
gph[v].push_back({ u,w });
}
int root = dfs(1, 0, 0).snd;
int ans = -dfs(root, 0, 0).fst.snd;
printf("%d\n", (ans + t - 1) / t);
return 0;
}
I. 하늘에서 별똥별이 빗발친다
풀이
최대한의 별똥별들을 튕겨내기 위해 트램펄린을 놓는 어떤 최적해가 있다고 하자.
최적해는 반드시 하나 이상이 존재할 수 있다.
최적해에 들어있는 모든 별똥별들을 포함하기만 한다면, 트램펄린의 위치를 바꾸어도 여전히 최적해이다.
그리고 항상 트램펄린을 이웃한 두 모서리에 두 개의 별이 걸쳐지도록 배치할 수 있다. (최소한 꼭짓점이라도)
따라서, 임의의 두 별똥별 쌍에 트램펄린을 걸치게 배치하고
트램펄린의 영역 내에 들어있는 별똥별의 개수를 구하면 된다.
별똥별은 항상 100개 이하이므로, O(K^3)의 시간에 문제를 해결할 수 있다.
코드
#include <bits/stdc++.h>
using namespace std;
int n, m, l, k, res;
struct ABC { int x, y; } pos[101];
void gogo(int x, int y) {
int cnt = 0;
for (int i = 0; i < k; i++) {
if (x <= pos[i].x && pos[i].x <= x + l &&
y <= pos[i].y && pos[i].y <= y + l) ++cnt;
res = max(res, cnt);
}
}
int main() {
scanf("%d %d %d %d", &n, &m, &l, &k);
for (int i = 0; i < k; i++)
scanf("%d %d", &pos[i].x, &pos[i].y);
for (int i = 0; i < k; i++) for (int j = 0; j < k; j++)
gogo(pos[i].x, pos[j].y);
printf("%d", k - res);
return 0;
}
J. 한조서열정리하고옴ㅋㅋ
풀이
활잡이들은 무조건 왼쪽에서 오른쪽으로 용을 보낸다.
높이가 (a < b)이고 순서가 (a … -> … b)인 봉우리가 있다고 하자.
a에서 출발한 용이 b에 가로막혔다고 가정하면
a는 항상 a와 b사이에 있는 활잡이들보다 더 많은 적을 처치할 수 있다.
a가 b에 도착했다는 건, a와 b 사이에는 a보다 낮은 봉우리들 밖에 없다는 뜻이기 때문이다.
왼쪽에 있는 활잡이부터 시작해서, 자기보다 더 높은 봉우리를 만날 때까지 카운팅 해주고 max를 구하면 된다.
코드
#include <stdio.h>
const int n_ = 3e4 + 3;
int n, ans, cnt, prv;
int main() {
int i, pos[n_];
scanf("%d", &n);
for (i = 0; i < n; i++) scanf("%d", &pos[i]);
for (i = 1; i < n; i++) {
if (pos[prv] > pos[i]) ans = ans > ++cnt ? ans : cnt;
else prv = i, cnt = 0;
}
printf("%d", ans);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, wookje, 욱제, 풀이, 선린, 선린인터넷고등학교, sunrin, 문제 풀이, 제1회 천하제일 코딩대회, 준오, 임준오, junoim, 이시훈, 김영중, 한화, 행복수비, 한조, 파라, 꺄르르르르ㅡㄱ