저자 자체 제작 문제는 저작권을 위해 문제를 작성하지 않았음을 알립니다.
Q.01 모험가 길드
문제
<저작권을 보호하기 위해 문제는 올리지 않습니다.>
문제접근
- 최대한 많은 그룹을 만들기 위해서는 어떻게 해야하는지 생각해야 한다.
- 모험가들의 공포도를 오름차순으로 정렬한 뒤 적은 공포도를 가지고 있는 사람부터 그룹을 만드는 경우가 최대 그룹을 만들 수 있는 경우다.
코드
#include <iostream>
#include <algorithm>
using namespace std;
int N, arr[100001];
int main() {
cin >> N;
for (int i = 1; i <= N; ++i) cin >> arr[i];
sort(arr.begin(), arr.end());
int result = 0; // 총 그룹의 수
int count = 0; // 현재 그룹에 포함된 모험가의 수
for (int i = 0; i < N; i++) { // 공포도를 낮은 것부터 하나씩 확인하며
count += 1; // 현재 그룹에 해당 모험가를 포함시키기
if (count >= arr[i]) { // 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
result += 1; // 총 그룹의 수 증가시키기
count = 0; // 현재 그룹에 포함된 모험가의 수 초기화
}
}
cout << result << '\n'; // 총 그룹의 수 출력
}Q.02 곱하기 혹은 더하기
문제
각 자리가 숫자로만 이뤄진 문자열 S가 주어졌을 때, 각 숫자 사이에 곱셈기호 또는 덧셈기호를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하시오.
e.g) 02984 = (((0 + 2) * 9) * 8) * 4) = 576 (MAX)
문제접근
- 곱셈을 해서는 안되는 경우가 언제인지만 떠올리면 쉽게 해결할 수 있는 문제다.
- 이므로 숫자
0이 들어가는 경우 무조건 덧셈을 해주는게 최선이다. 또한 이므로 숫자1이 들어가는 경우도 덧셈을 해주는게 최선이다. - 또는, 문자열 S의 길이가 길지 않기 때문에
max()함수를 이용해서 무작정 계산하는 것도 하나의 방법이다.
코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
string input; cin >> input;
vector<int> seq(input.length());
for (int i = 0; i < input.length(); ++i) seq[i] = input[i] - '0';
unsigned long long ans = seq[0];
for (int i = 1; i < input.size(); ++i) {
int temp = input[i] - '0';
ans = max(ans + temp, ans * temp);
}
cout << ans << '\n';
}Q.03 문자열 뒤집기
문제
https://www.acmicpc.net/problem/1439
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다.
4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.
문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.
문제접근
- 접근법이 잘 떠오르지 않는 까다로운 문제다.
- 이 문제를 쉽게 풀기 위해서는 연속된 같은 숫자를 하나의 그룹으로 생각하는 것이다.
0그룹과1그룹으로 나누고, 문자열을 앞에서부터 읽으면서 각 그룹을 카운트한다.- 두 그룹 중 카운트 수가 적은 그룹의 카운트 수가 정답이된다.
코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
string input; cin >> input;
vector<bool> S(input.length());
for (int i = 0; i < input.length(); ++i)
S[i] = (input[i] == '0') ? false : true;
int count0 = 0, count1 = 0; // 0그룹, 1그룹의 개수 저장 변수
(S[0]) ? count1++ : count0++; // 초기값 설정하기
for (int i = 1; i < S.size(); ++i) {
if (S[i - 1] != S[i]) { // 이전값이랑 다르면 그룹 개수 갱신해야 함.
if (S[i]) count1++; // 1그룹 개수 추가
else count0++; // 0그룹 개수 추가
}
}
cout << min(count0, count1) << '\n';
}Q.04 만들 수 없는 금액
문제
<저작권을 보호하기 위해 문제는 올리지 않습니다.>
문제접근
- 오히려 주어진 동전들로 만들 수 있는 금액을 모두 탐색한다.
- 만든 금액을 오름차순으로 정렬한다.
1부터 시작해서 만들 수 없는 금액을 탐색하는 방법이 유효하다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, coin[1000];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> N;
for (int i = 0; i < N; ++i) cin >> coin[i];
// 과정 1: 주어진 동전들의 모든 조합을 계산하고 vec 배열에 넣는다.
sort(coin, coin + N);
vector<int> vec;
for (int i = 0; i < N; ++i)
for (int j = i; j < N; ++j) {
int temp = 0;
for (int k = i; k <= j; ++k) temp += coin[k];
vec.push_back(temp);
}
// 과정 2: vec 배열을 오름차순으로 정렬한다.
sort(begin(vec), end(vec));
// 과정 3: i-1번째 요소와 i번째 사이에 자연수가 있다면 그게 정답이다.
if (vec[0] == 1) { // 가장 작은 요소가 1이라면 자연수를 찾아야 한다.
int ans = vec[0];
for (int i = 1; i < vec.size(); ++i)
if (vec[i] - vec[i - 1] > 1) {
ans = vec[i - 1] + 1;
break;
}
cout << ans << '\n';
} // 가장 작은 요소가 1보다 크다면 1이 최솟값이다.
else cout << 1 << '\n';
}Q.05 볼링공 고르기
문제
<저작권을 보호하기 위해 문제는 올리지 않습니다.>
문제접근
- 쉬운 그리디 문제이지만, 범위가 1000까지로 적은 편이므로 bruteforce를 사용해서 풀었다.
- 모든 조합을 계산하고, 선택한 두 볼링공의 무게가 다른 경우만 카운트 해주면 된다.
코드
#include <iostream>
using namespace std;
int N, M, ball[1000];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> N >> M;
for (int i = 0; i < N; ++i) cin >> ball[i];
int ans = 0;
for (int i = 0; i < N; ++i)
for (int j = i + 1; j < N; ++j)
if (ball[i] != ball[j]) ans++;
// 모든 조합에서 두 값이 같은 조합은 무시한다.
cout << ans << '\n';
}Q.06 무지의 먹방 라이브
문제
https://www.welcomekakao.com/learn/courses/30/lessons/42891
문제접근
- 이 문제의 관건은
K의 상한이 너무 크기 때문에K초를 어떻게 가장 빠른 방법으로 줄여나갈 것인지 알아내는 것이다. - 이 문제의 핵심은 딱 하나다!
가장 소요 시간이 적은 음식을 다 먹을 때까지는 전체 음식 개수만큼 순회한다는 것이다. 그 다음부터는 가장 소요 시간이 적은 음식은 없어지고 그 다음 번 음식을 다 먹을 때까지 나머지 전체 음식 개수만큼 순회할 것이다.
- 처음에
5, 9, 8, 3, 11만큼 소요되는1, 2, 3, 4, 5번 음식이 주어졌다고 하자. K = 20일 때 몇 번 음식을 먹고 있는지가 궁금하다. - 먼저, 음식을 소요시간에 대해 오름차순으로 정렬한다.
3초로 가장 소요 시간이 적은 4번 음식을 다 먹을 때 까지는 전체를 순회하게 된다. 순회하면서 초만큼 시간이 소요된다.- 15초가 지났다. 4번 음식은 다 먹었고, 이제 전체 음식 개수는 5개에서 4개가 됐고, K는 20에서 15를 뺀 5가 됐다.
- 그 다음으로 소요 시간이 적은 1번 음식은 2초만 더 먹으면 다 먹게된다. 그러나 남은 시간은 5초인데 남은 음식 개수가 4개이므로 이므로 순회할 시간이 모자란다.
- 그러므로 순회하지말고 5초일 때 몇 번 음식을 먹고 있는지 계산하자. 다시 음식을 번호 순서에 따라 오름차순으로 정렬한다.
- 마지막으로, 5번째 음식이 '몇 번' 음식일지 계산해보자. 1번 음식이다.
- 결과적으로,
K = 20일 때 먹는 음식은 1번 음식이라는 것을 알 수 있다.
코드
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int solution(vector<int> food_times, long long k) {
priority_queue<pair<int, int>> pq; // min heap, deque를 써도 된다.
long long sum = 0, prevValue = 0;
for (int i = 0; i < food_times.size(); ++i) {
sum += food_times[i];
pq.push({-food_times[i], i + 1});
}
if (sum <= k) return -1; // 총 시간이 k보다 작다면 모두 먹을 수 있다.
// <과정 1>: 적절한 k값을 빠르게 감산하며 구한다.
while ((-pq.top().first - prevValue) * pq.size() <= k) {
k -= (-pq.top().first - prevValue) * pq.size();
prevValue = -pq.top().first;
pq.pop();
}
// <과정 2>: 정답을 찾기위해 random-access container에 저장한다.
vector<pair<int, int>> ans;
while (!pq.empty()) {
// 음식 번호 순서대로 나중에 정렬하기 위해 second와 first를 바꿔 저장.
ans.push_back({pq.top().second, -pq.top().first});
pq.pop();
}
sort (begin(ans), end(ans)); // 음식 번호 순서대로 정렬한다.
return ans[k % ans.size()].first; // k번째 음식 번호를 반환한다.
}- 처음에 음식번호와 시간을 저장하면서 시간의 합을 계산한다. 이때 시간의 총합이 k보다 작다면 모든 음식을 먹을 수 있다.
- 식사 소요시간이 적은 순으로 정렬하기 위해 min heap을 사용했다.
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;로 쓰면 굳이 소요시간에 음수를 붙히지 않고도 min heap을 구현할 수 있다.
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.