개괄
코테 대비를 위해 대회 형식의 연습도 필요할 듯하여 3시간 제한으로 진행하였다. 제4회 SMUPC의 문제를 사용하였고, 싸지방에 모여서 진행했으나 중간에 뇌우조치로 작업가야해서(…) 흐름이 끊기긴 했다.
A번. SMUPC NAME (BOJ 31859) (브론즈 1)
#implementation #string
내 풀이
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int alphabet[26]; // 'a'->0에 대응, 사용됐을 경우 1
int isAvailable[21]; // 제거할 시 1
int main() {
string name; // 최대 20자
string nickname = "";
int N;
int cnt = 0; // 제거 문자 수
cin >> N;
cin >> name;
for(int i = 0; i < name.length(); i++){
if(alphabet[name[i] - 'a'] == 0) alphabet[name[i] - 'a'] = 1;
else{
cnt++;
isAvailable[i] = 1;
}
}
for(int i = 0; i < name.length(); i++){
if(isAvailable[i] == 0) nickname += name[i];
}
cnt += 4;
nickname += to_string(cnt);
N += 1906;
nickname = to_string(N) + nickname;
reverse(nickname.begin(), nickname.end());
nickname = "smupc_" + nickname;
cout << nickname;
return 0;
}개선된 풀이
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
string name;
cin >> name;
// 알파벳 사용 여부를 저장하는 벡터 (false: 아직 안 씀, true: 이미 사용됨)
vector<bool> used(26, false);
// 중복되지 않는 문자를 담을 문자열
string filteredName;
// 중복된 문자(두 번째 이상 등장한 문자) 개수
int duplicateCount = 0;
for (char c : name) {
int idx = c - 'a';
// 아직 사용되지 않은 알파벳이라면
if (!used[idx]) {
used[idx] = true;
filteredName.push_back(c);
} else {
// 이미 사용된 알파벳이면 중복 문자 수 증가
duplicateCount++;
}
}
// 문제 요구사항에 따라 중복 문자 수에 4를 더함
duplicateCount += 4;
// N에 1906을 더함
N += 1906;
// 닉네임: (N값) + (중복 제거된 문자열) + (중복 문자 수)
string nickname = to_string(N) + filteredName + to_string(duplicateCount);
// 문자열 뒤집기
reverse(nickname.begin(), nickname.end());
// "smupc_"를 접두어로 추가
nickname = "smupc_" + nickname;
// 결과 출력
cout << nickname << "\n";
return 0;
}✅ 풀면서 느낀 점
- 빠르게 풀고 넘겼어야 할 A번 문제이지만, string 오랜만에 다루면서 구현에 어려움을 겪고 16분 걸림
-> String 문제 풀 것!
B번. 열심히 일하는 중 (BOJ 31860) (실버 2)
#implementation #data_structures #simulation #priority_queue
내 풀이
/*
일의 수: N
일 처리 후 M만큼 중요도 감소
중요도 K 이하로 떨어지면 그 일은 완료.
만족도 = (전날 만족도 / 2) + 오늘 한 일 중요도
(첫날의 경우 전날 만족도 0으로 가정)
Goal1: 일 끝내는데 얼마나 걸림?
Goal2: 매일매일 만족도
Idea: priority_queue를 활용해보자!
*/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
priority_queue<int> work; // 중요도 크기 내림차순으로 정렬
vector<int> daily_satisfaction;
int main() {
int N, M, K;
int tmp;
int day = 0; // 업무 끝나는 데 걸리는 일 수
int satisfaction = 0; // 전날 만족도
cin >> N >> M >> K;
for(int i = 0; i < N; i++){
cin >> tmp;
work.push(tmp);
}
while(!work.empty()){
int importance = work.top();
day++;
work.pop();
satisfaction = satisfaction / 2 + importance;
daily_satisfaction.push_back(satisfaction);
importance -= M;
if(importance > K) work.push(importance);
}
cout << day << '\n';
for(auto &k : daily_satisfaction){
cout << k << '\n';
}
return 0;
}✅ 풀면서 느낀 점
- 16분 소요 -> 무난하게 넘김!
- 문제 접근: ‘매 순간 중요도가 제일 높은 작업 택해야함‘
-> ‘중요도 순으로 항상 정렬‘
->priority queue! - 코테 때 나올 문제도 텍스트양이 많아 독해를 빠르게 잘 하는 것이 관건일 것 -> 문제의 조건 써보면서 문제 이해하기!
C번. 비밀번호 만들기 (BOJ 31861) (실버 1)
#dp
내 풀이
/*
IDEA: DP 문제?!
DP[n][k]
n번째 문자(1<=n<=26) 뒤에 문자열 길이 k (0<=k<1000) 경우의수
기저사례
DP[n][0] = 1
DP[n][1] = {현재 문자: x, 가능한 범위: 1<=a<=26 , |a-x| >= N}일 때 a의 개수
Given N, M
=> we need to find DP[1][M-1] + DP[2][M-1] + ... + DP[26][M-1]!
*/
#include <iostream>
using namespace std;
int DP[27][1000];
int N, M;
int findDP(int a, int b);
int main() {
int sum = 0; // 구하고자 하는 경우의 수
cin >> N >> M;
// DP배열 초기화
for(int i = 1; i <= 26; i++){
for(int j = 0; j <= M - 1; j++){
DP[i][j] = -1;
}
}
for(int i = 1; i <= 26; i++){
sum = (sum + findDP(i, M-1)) % 1000000007;
}
cout << sum;
return 0;
}
int findDP(int a, int b){
if(DP[a][b] != -1) return DP[a][b];
else if(b == 0){
DP[a][b] = 1;
return 1;
}
else if(b == 1){
int cnt = 0;
for(int i = 1; i <= 26; i++){
if(abs(i - a) >= N) cnt++;
}
DP[a][b] = cnt;
return cnt;
}
else{
int sum = 0;
for(int i = 1; i <= 26; i++){
if(abs(i - a) >= N){
sum = (sum + findDP(i, b - 1)) % 1000000007;
}
}
DP[a][b] = sum;
return sum;
}
}✅ 풀면서 느낀 점
- 28분 소요 -> 잘 풀었음!
- 문제 접근: ‘가능한 경우의 수 카운팅‘ + ‘int형 범위 초과하는 정답‘
->DP를 사용하지 않을까?
-> 무엇을 기록(재사용)해야 할까? - DP 문제를 풀 때 구해야 할 2가지
점화식기저사례(base case)
더 구하기 쉬운 기저사례를 먼저 떠올리고 점화식에 접근하니 잘 풀 수 있었음!
D번. 내진 설계 (BOJ 31863) (골드 5)
#graphs #graph_traversal #implementation #simulation
내 풀이 (대회 시간 후 완성)
/*
IDEA: 시키는 그대로 하자!
지진의 종류가 2개. → 본진(2칸) & 여진(1칸)
핵심 → 본진은 어차피 처음 1번만! 이후에는 여진만 발생 가능.
→ 본진을 따로 처리해주고, 여진을 queue로 처리해주자!
*/
#include <iostream>
#include <queue>
using namespace std;
char Map[1001][1001];
struct Position{
int x, y;
};
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
queue<Position> q;
int collapse = 0; // 무너진 건물 수
// 건물 만났을 때 처리 방식 똑같으므로 함수로 처리해주자!
void WeakBuilding(int x, int y);
void StrongBuilding(int x, int y);
int main() {
int N, M;
int num = 0; // 기존 건물 수
Position source;
cin >> N >> M;
// 맵 입력받기 & 진원지 찾아주기
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> Map[i][j];
if(Map[i][j] == '@'){
source.x = i;
source.y = j;
}
else if(Map[i][j] == '*' || Map[i][j] == '#') num++;
}
}
// 본진 처리해주기
for(int i = 0; i < 4; i++){
int pointx = source.x + dx[i];
int pointy = source.y + dy[i];
if(pointx >= 0 && pointx < N && pointy >= 0 && pointy < M){
// 방파제일 경우 -> 여기서 끝!
if(Map[pointx][pointy] == '|') continue;
// 내진X 건물 -> 건물 무너짐 & 여진 발생!
else if(Map[pointx][pointy] == '*') WeakBuilding(pointx, pointy);
// 내진O 건물 -> 내진X 건물로 바뀜!
else if(Map[pointx][pointy] == '#') StrongBuilding(pointx, pointy);
// 방파제 아닌 case이므로 => 두 칸 갈 수 있는지 체크!
pointx += dx[i];
pointy += dy[i];
if(pointx >= 0 && pointx < N && pointy >= 0 && pointy < M){
if(Map[pointx][pointy] == '*') WeakBuilding(pointx, pointy);
else if(Map[pointx][pointy] == '#') StrongBuilding(pointx, pointy);
}
}
}
// 여진 처리해주기
while(!q.empty()){
int pointx = q.front().x;
int pointy = q.front().y;
q.pop();
for(int i = 0; i < 4; i++){
int newpointx = pointx + dx[i];
int newpointy = pointy + dy[i];
if(newpointx >= 0 && newpointx < N && newpointy >= 0 && newpointy < M){
if(Map[newpointx][newpointy] == '|') continue;
else if(Map[newpointx][newpointy] == '*') WeakBuilding(newpointx, newpointy);
else if(Map[newpointx][newpointy] == '#') StrongBuilding(newpointx, newpointy);
}
}
}
cout << collapse << ' ' << num - collapse;
return 0;
}
void WeakBuilding(int x, int y){
collapse++;
Map[x][y] = '.';
Position tmp;
tmp.x = x;
tmp.y = y;
q.push(tmp);
}
void StrongBuilding(int x, int y){
Map[x][y] = '*';
}✅ 풀면서 느낀 점
- 이 문제에서 시간을 꽤 소요했고, 결정적으로 풀었음에도 WA(Wrong Answer)가 나와 멘붕이 오면서 나머지 문제를 못 풀고 이 문제마저 해결하지 못하게 되었다.
- 로직이 어려운 문제가 전혀 아니었고, 내가 생각한 바와 같이 ‘시키는 대로‘ 하면 되는 문제였다.
- 어이없게도 내 로직 역시 맞았고,
int num = 0;을int num;으로 쓴 것 하나만이 문제였다. - 온라인 컴파일러를 사용하였는데, 주어진 예제도 맞고, 내가 만든 사이드케이스 역시 문제없이 실행됐던 이유는 아마 컴파일러 버전이 높아 초기화하지 않은 변수를 0으로 알아서 초기화했기 때문(?)으로 생각한다.
🧠 피드백
이 문제에서 발생한 패착은 크게 2가지
1. 로직이 어렵지 않았음에도 최초풀이를 완성하는 데 시간이 걸린 점
2. 테케가 맞았음에도 WA가 나오는 상황에 대처하지 못한 점
이다.
1번의 문제는 결국 집중력 문제로, 제한된 시간 안에 빠르게 문제를 정확히 푸는 훈련을 많이 하는 것이 주요할 것으로 보인다.
(수능에 비유하자면, 80분 동안 국어 시험지 한 세트를 푸는 연습)
2번의 문제는 Online Judge와 내가 사용한 컴파일러의 환경이 다를 수 있다는 점을 몰랐던 것, 그리고 내 코드를 꼼꼼히 디버깅하지 못한 점에서 기인한다.
‘ 어떤 전략을 세울 것인가? ‘와도 결부된다. 분명히 내 로직이 맞다는 확신이 있음에도 미상의 원인으로 WA가 뜰 때, 뒷 문제들 또한 로직을 바로 떠올릴 수 있다면 일단 뒷 문제부터 푸는 것이 좋은 전략이 되겠지만, 뒤의 문제들이 쉽게 풀기 힘든 난이도라면 이 문제는 절대 틀려서는 안 될 문제일 것이고, 코드를 처음부터 파헤쳐 봤어야 했다. 앞으로 같은 경우가 발생한다면 변수 선언에서 문제가 없는 지도 꼭 체크해야겠다.
나머지 문제들은 시간 내에 읽지 못했거나, 조금 접근하다 말았음으로 개별 문제를 따로 푼 후 피드백할 예정이다.
어제보다, 더