[BOJ] 랜덤 마라톤 (No. 24723, 21603, 2567, 23827, 31474, 1182, 6106, 30106)
by 구설구설24723
문제
녹색거탑
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2.022 초 (추가 시간 없음) 319 MB (추가 메모리 없음) 15937 10575 9947 66.898%
문제
Naver D2를 아시나요? D2는 For Developers, By Developers의 약자로, 개발자들을 위해 개발자들이 직접 만들어 가고 있는 네이버 개발자 지원 프로그램입니다. 네이버가 축적한 기술과 지식을 공유하고, 외부 개발자들을 지원해 대한민국 개발자 역량 강화를 이끌고, 이를 통해 업계 전체와 네이버가 함께 성장하는 선순환 구조를 만들고자 합니다.
사실 네이버의 개발자 지원은 오랜 기간 꾸준히 이어져 왔습니다. 개발자 컨퍼런스 DEVIEW를 비롯, 오픈 소스와 개발 도구 공개, 학회 및 커뮤니티 지원 등 여러 지원 프로그램이 있었습니다. 이런 다양한 프로그램을 하나로 통합한 것이 바로 Naver D2입니다.
2022년 봄 어느 날.
전 세계에 코딩괴물이 나타났다.
그리고 코딩괴물과 함께 갑작스레 등장한 '그것'...
바로 녹색거탑이다.
녹색거탑의 정상에서는 매년 NAVER가 개최하는 개발자 컨퍼런스 DEVIEW가 열린다. 이 DEVIEW에 참여하면, 코딩에 깊은 깨달음을 얻어 코딩괴물이 될 수 있다고 전해진다. 그리고 코딩괴물은 녹색거탑의 정상에서 내려온다. 예전부터 전해 내려오는 D2 비전서에 의하면, 코딩괴물이 녹색거탑의 정상에서 내려오는 경우의 수를 파악한 사람은, 개발자 컨퍼런스 DEVIEW에 참여할 수 있다 한다. 그리고 DEVIEW에 참여해 본인도 코딩괴물이 될 수 있다!
녹색거탑은 위 그림과 같이 규칙적으로 쌓여있다.
그림의 시야에 보이지 않는 블록은 없다.
그림의 시야에 보이는 블록의 윗면만 이용해 녹색거탑을 내려올 수 있다.
녹색거탑이 N층이면, 총 N개의 블록을 이용한 최단 경로로만 내려온다.
녹색거탑을 내려올 때는 정상에서 시작해 노란색 바닥까지, 항상 인접한 아래층의 블록으로만 내려온다.
녹색거탑을 정복하고 DEVIEW에 참여하자.
입력
녹색거탑의 높이를 나타내는 정수
N이 주어진다.
(1 <= N <= 5)
출력
녹색거탑의 정상에서 바닥으로 내려오는 경우의 수를 출력한다.
예제 입력 1
1
예제 출력 1
2
예제 입력 2
2
예제 출력 2
4풀이
한번 내려갈 때 2가지의 선택지가 있으므로 총 $2 ^ N$가지가 나온다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
cout << pow(2, n) << '\n';
}
21603
문제
K 2K 게임
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 256 MB 1102 643 560 61.135%
문제
싸이컴에서는 신입생의 집중력을 테스트하기 위해 아래와 같은 간단한 게임을 개발했습니다.
두 정수 N과 K가 주어집니다.
자연수 x에 대해 f(x)를 x의 일의 자리 수라고 할 때, f(x) < f(K)이고 f(x) < f(2K)인
1 이상 N 이하의 정수 x를 오름차순으로 모두 말합니다.
당신은 일의 자리 수를 일일이 계산하기 귀찮기 때문에, 몰래 프로그램을 만들어 게임에서 승리하려고 합니다. 말해야 하는 수의 목록을 모두 출력하는 프로그램을 만들어 봅시다.
입력
두 정수 N과 K가 띄어쓰기를 사이에 두고 주어집니다.
출력
첫 줄에는 당신이 말해야 할 수의 개수를 출력합니다.
둘째 줄에는 당신이 말해야 할 수를 한 줄에 모두 출력합니다. 만약 말해야 할 수가 없다면, 둘째 줄은 비워둡니다. 수는 크기 순서대로 출력해야 합니다.
제한
1 <= N, K <= 10^5
예제 입력 1
9 4
예제 출력 1
7
1 2 3 5 6 7 9
예제 입력 2
16 12
예제 출력 2
12
1 3 5 6 7 8 9 10 11 13 15 16
풀이
$m$과 $m*2$의 일의 자리 수와 $N$이하의 자연수의 일의 자리 수가 동일하지 않다면 정답 벡터에 저장한 후,
정답 벡터의 사이즈와 벡터의 요소를 출력하면 된다.
#include <bits/stdc++.h>
using namespace std;
int filter[2];
vector<int> result;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
filter[0] = m % 10;
filter[1] = (m * 2) % 10;
for (int i = 1; i <= n; i++) {
if (i % 10 != filter[0] && i % 10 != filter[1]) {
result.push_back(i);
}
}
cout << result.size() << '\n';
for (int i = 0; i < result.size(); i++) {
cout << result[i] << ' ';
}
}
2567
문제
색종이 - 2
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 11802 5199 4111 43.434%
문제
가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 둘레의 길이를 구하는 프로그램을 작성하시오.
예를 들어 흰색 도화지 위에 네 장의 검은색 색종이를 <그림 1>과 같은 모양으로 붙였다면 검은색 영역의 둘레는 96 이 된다.
입력
첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다.
출력
첫째 줄에 색종이가 붙은 검은 영역의 둘레의 길이를 출력한다.
예제 입력 1
4
3 7
5 2
15 7
13 14
예제 출력 1
96풀이
처음에는 둘레를 직접 계산하는 방식으로 접근이 가능할 줄 알았다.
#include <bits/stdc++.h>
using namespace std;
int n, ans;
vector<pair<int, int>> v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
ans += 40;
for (int j = 0; j < v.size(); j++) {
if (abs(v[j].first - x) <= 10 && abs(v[j].second - y) <= 10) {
ans -= 2 * (10 - abs(v[j].first - x) + 10 - abs(v[j].second - y));
}
}
v.push_back({x, y});
}
cout << ans << '\n';
}그런데 이렇게 풀면 3개 이상의 색종이의 면적이 겹치는 경우를 고려할 수 없었다.
아래는 반례이다.
5
0 0
10 0
0 10
10 10
5 5그래서 배열을 탐색하는 방식으로 변경하였다.
전체 도화지를 이중 for 문으로 탐색하면서 값이 1인 경우 상하좌우를 확인하면서 0이면 테두리로 간주한다.
#include <bits/stdc++.h>
using namespace std;
int n, ans;
int paper[101][101];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
for (int j = x; j < x + 10; j++) {
for (int k = y; k < y + 10; k++) {
paper[j][k] = 1;
}
}
}
for (int i = 0; i < 101; i++) {
for (int j = 0; j < 101; j++) {
if (paper[i][j] == 1) {
if (paper[i - 1][j] == 0) ans++;
if (paper[i + 1][j] == 0) ans++;
if (paper[i][j - 1] == 0) ans++;
if (paper[i][j + 1] == 0) ans++;
}
}
}
cout << ans << '\n';
}
23827
문제
수열 (Easy)
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 512 MB 2685 927 738 34.041%
문제
모든 원소가 양의 정수이고, 길이가 N인 수열 A_1, A_2, ..., A_N이 주어진다.
1 <= i < j \<= N을 만족하는 모든 정수쌍 (i, j)에 대해 A_i * A_j의 합을 1,000,000,007로 나눈 나머지를 구하시오.
입력
첫째 줄에 수열 A의 길이 N이 주어진다.
둘째 줄에 수열 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
출력
1 <= i < j <= N을 만족하는 모든 정수쌍 (i, j)에 대해 A_i * A_j의 합을 1,000,000,007로 나눈 나머지를 출력하여라.
제한
2 <= N <= 500,000
1 <= A_i <= 500,000 (1 <= i <= N)
예제 입력 1
3
1 2 3
예제 출력 1
11풀이
처음에는 전체 합에서 자신을 제외한 값과 자신을 곱한 것을 더하고 나머지를 구한 다음 2로 나누는 방법을 사용하려고 했다.
그런데 나머지를 구한 후 2로 나누면 정확한 값이 나오지 않는다는 것을 깨닫고 ~누적 합~으로 방법을 변경하였다.
#include <bits/stdc++.h>
using namespace std;
long long n, sum, ans;
const int MOD = 1000000007;
vector<long long> a;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
ans = (ans + (sum * a[i])) % MOD;
sum += a[i];
}
cout << ans << '\n';
}입력 이전까지의 합과 입력된 값을 곱한 뒤,
기존의 정답에 더하고 나머지를 구하면 된다.
31474
문제
양갈래 짝 맞추기
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 1024 MB 457 283 257 67.454%
문제
시현이 카페에 양갈래 손님들이 들어가려고 한다.
양갈래 손님들은 양갈래를 너무 좋아하는 나머지 두 명씩 모여 있어 총 인원은 짝수이다.
시현이 카페에는 두 명씩 앉을 수 있는 테이블이 충분히 많이 있고, 양갈래 손님들은 한 테이블에 두 명씩 앉기로 하였다.
그런 양갈래 손님들을 맞이하게 된 시현이는 갑자기 궁금증이 생겼다.
손님들이 앉는 경우의 수를 세는 조건이 다음과 같을 때, 양갈래 손님들이 모두 앉을 수 있는 방법의 수는 몇 가지가 있을까?
테이블의 좌석을 구분하지 않는다.
한 테이블에서 손님 A와 손님 B가 앉는 경우, 손님 B와 손님 A가 앉는 경우는 같은 경우이다.
각각의 테이블 또한 구분하지 않는다.
1번 테이블에 손님 A, B가 앉고, 2번 테이블에 손님 C, D가 앉는 것과, 1번 테이블에 손님 C, D가 앉고, 2번 테이블에 손님 A, B가 앉는 것은 서로 같은 경우이다.
입력
첫째 줄에 양갈래 손님의 수 N이 주어진다. (2 <= N \<= 28, N은 짝수)
출력
첫째 줄에 양갈래 손님들이 앉을 수 있는 경우의 수를 출력한다.
연산 중 32비트 정수형 타입의 표현 범위를 초과할 수 있으므로 오버플로우에 주의한다.
예제 입력 1
2
예제 출력 1
1
예제 입력 2
4
예제 출력 2
3풀이
고등학교 시간에 많이 보았던 같은 수로 나누는 조합의 경우의 수를 구하는 문제이다.
$ ( nC_2 + _{n-2}C_2 + ... + _{2}C_2 ) / (n/2)! $ 를 구하면 된다.
#include <bits/stdc++.h>
using namespace std;
long long n, ans = 1, cnt;
long long combination(long long n, long long r) {
if (r == 0 || n == r) return 1;
if (r == 1) return n;
return combination(n - 1, r - 1) + combination(n - 1, r);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
while (n > 0) {
ans *= combination(n, 2);
n -= 2;
cnt++;
ans /= cnt;
}
cout << ans << '\n';
}
1182
문제
부분수열의 합
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 256 MB 95933 43485 28358 43.366%
문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
예제 입력 1
5 0
-7 -3 -2 5 8
예제 출력 1
1풀이
$2^N$ 만큼 for 문을 돌려도 시간초과가 나지 않기 때문에 돌렸다.
i를 비트 연산을 하여서 모든 부분 집합의 합을 구해서 경우의 수를 계산하였다
#include <bits/stdc++.h>
using namespace std;
long long n, m, ans;
vector<long long> v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
v.resize(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
for (int i = 1; i < pow(2, n); i++) {
long long sum = 0;
int temp = i;
for (int j = 0; j < n; j++) {
if (temp % 2 == 1) {
sum += v[j];
}
temp /= 2;
}
if (sum == m) {
ans++;
}
}
cout << ans << '\n';
}비트 연산자를 사용하는 방법도 있다.
#include <bits/stdc++.h>
using namespace std;
long long n, m, ans;
vector<long long> v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
v.resize(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
for (int i = 1; i < pow(2, n); i++) {
long long sum = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
sum += v[j];
}
}
if (sum == m) {
ans++;
}
}
cout << ans << '\n';
}~if (i & (1 << j))~ 는 i의 이진수 표현에서 j번째 비트가 1이면, 배열 v의 j 번째 요소가 현재 고려하는 부분 집합에 포함된다는 뜻이다.
동작 결과는 위 코드와 동일하다.
6106
문제
Payback
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 249 92 81 38.756%
문제
"결코 빌려주지도 빌리지도 말라"라는 충고를 Bessie가 따랐더라면 얼마나 좋았을까! Bessie는 N명의 친구(1 ≤ N ≤ 100,000)에게 돈을 빌리거나 빌려주었다. 이 친구들은 편리하게 1번부터 N번까지 번호가 붙어 있다.
드디어 갚는 날이 왔다. Bessie는 자신이 빌린 돈보다 빌려준 돈이 더 많다는 것을 알고 있다. 친구들은 일렬로 줄을 섰으며, i번째 친구는 헛간(위치 0)으로부터 i 미터 떨어진 곳에 서 있다. Bessie는 줄을 따라 이동하며 돈을 빌려준 친구들에게는 돈을 받아내고, 빚을 진 친구들에게는 돈을 갚아야 한다.
Bessie는 줄을 따라 이동하며 다음 작업을 수행할 수 있다:
돈을 받을 수 있음: 빌려준 돈이 있는 친구로부터 돈을 받는다.
돈을 갚을 수 있음: 빚을 진 친구에게 돈을 갚는다. 받은 돈이 충분할 경우 빚을 갚는다.
각 i번째 친구는 Bessie에게 D_i만큼의 돈을 빚졌다. D_i의 값이 음수일 경우, 이는 Bessie가 그 친구에게 돈을 빚진다는 것을 의미한다. (-1,000 ≤ D_i ≤ 1,000, D_i ≠ 0)
Bessie는 헛간(위치 0)에서 시작하며, 줄의 끝(N번 친구 위치)에서 여행을 마쳐야 한다. 모든 빚을 갚거나 받아야 하는 상황에서, Bessie가 이동해야 하는 최소 거리를 계산하라.
입력
첫 번째 줄: 정수 N (친구의 수)
두 번째 줄부터 N개의 줄: 각 줄에 정수 D_i (i번째 친구와의 돈 관계)
출력
한 줄에 Bessie가 이동해야 하는 총 거리의 최소값을 출력한다.
예제 입력 1
5
100
-200
250
-200
200
예제 출력 1
9풀이
그리디 문제이다.
현재 금액이 마이너스가 되는 위치를 저장해 놓았다가 다시 플러스가 되는 위치에서 두 위치의 차이를 2배 해서 움직인 거리에 더하면 된다.
다시 돌아가서 돈을 갚아야 하기 때문에...
#include <bits/stdc++.h>
using namespace std;
int n, pos, cur, cnt;
vector<int> v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
cur += v[i];
if (cur < 0) {
if (pos == -1) pos = i;
} else if (pos != -1) {
cnt += 2 * (i - pos);
pos = -1;
}
cnt++;
}
cout << cnt << '\n';
}
30106
문제
현이의 로봇 청소기
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 1024 MB 595 369 313 66.314%
문제
현이의 방은 매우 지저분하다! 현이는 선물로 로봇 청소기를 받았고, 귀찮은 청소를 맡기기로 했다.
로봇 청소기는 현이의 방을 1 x 1 크기의 정사각형으로 나누어져 있는 N x M 크기의 직사각형으로 인식한다.
로봇 청소기는 한 영역을 청소하고 나서 상, 하, 좌, 우로 인접한 영역 중 하나로 이동한다. 현이의 방은 오래되어 마루가 울퉁불퉁하고, 쓰레기도 눌러붙어 각 영역마다 높이가 조금씩 다르다. 로봇 청소기는 높이 차이가 K 초과인 두 영역 사이를 이동하면 고장이 날 수 있기 때문에, 높이 차이가 K 이하인 영역 사이에서만 이동한다.
현이는 외출하는 동안 로봇 청소기를 작동시키고 집에 돌아왔지만, 청소가 되지 않은 곳도 있는 것을 보고 실망했다.
결국 현이는 로봇 청소기의 위치를 직접 옮겨주기로 했다. 현이가 로봇 청소기를 직접 옮길 때는 아무 영역으로나 옮길 수 있다. 로봇 청소기를 켠 상태로 옮기면 위험하니 로봇 청소기를 끄고 옮긴 뒤에 다시 작동시킬 수 있다.
현이가 로봇 청소기를 최소 몇 번 작동시켜야 방의 모든 영역을 청소할 수 있을지 구해보자!
입력
첫 번째 줄에 자연수 N, M, K가 공백으로 구분되어 주어진다.
두 번째 줄부터 N+1번째 줄까지 각 영역의 높이를 나타내는 정수 M개가 공백으로 구분되어 주어진다.
출력
방의 모든 영역을 청소하기 위해 로봇 청소기를 작동시켜야 하는 최소 횟수를 출력한다.
제한
1 <= N, M <= 500
1 <= K <= 10^9
각 영역의 높이는 1 이상 10^9 이하이다.
예제 입력 1
2 3 2
5 4 6
4 7 2
예제 출력 1
3풀이
간단한 dfs 문제
이중 배열(시간초과 날 일은 없으니 벡터)에 집어 넣은 뒤
모두 돌면서 높이가 2 넘게 차이나는지 확인하면 된다.
#include <bits/stdc++.h>
using namespace std;
int n, m, k, ans;
vector<vector<int>> v;
vector<vector<int>> visited;
void dfs(int x, int y) {
if (visited[x][y] == 1) {
return;
}
visited[x][y] = 1;
if (y < m - 1 && visited[x][y + 1] == 0 && abs(v[x][y] - v[x][y + 1]) <= k) {
dfs(x, y + 1);
}
if (x < n - 1 && visited[x + 1][y] == 0 && abs(v[x][y] - v[x + 1][y]) <= k) {
dfs(x + 1, y);
}
if (y > 0 && visited[x][y - 1] == 0 && abs(v[x][y] - v[x][y - 1]) <= k) {
dfs(x, y - 1);
}
if (x > 0 && visited[x - 1][y] == 0 && abs(v[x][y] - v[x - 1][y]) <= k) {
dfs(x - 1, y);
}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m >> k;
v.resize(n);
visited.resize(n);
for (int i = 0; i < n; i++) {
v[i].resize(m);
visited[i].resize(m);
for (int j = 0; j < m; j++) {
cin >> v[i][j];
visited[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j] == 1) {
continue;
}
ans++;
dfs(i, j);
}
}
cout << ans << '\n';
}
'Algorithm > BOJ' 카테고리의 다른 글
블로그의 정보
공부중임
구설구설