뒷북이지만 올려보는 KPSC 후기

PS 갤러리
마이너

알고리즘 문제를 해결하는 Problem Solving을 다루는 갤러리입니다.

매니저

캐티(tae826)

부매니저

부재중입니다.(ailedear) Gravekper(gravekpe…) 옥토끼(moonrabb…) 나는최고(mebest)

개설일

2018-05-28

[일기] 뒷북이지만 올려보는 KPSC 후기앱에서 작성

행복을쫓아

2024.05.13 09:43:26

조회 354 추천 8 댓글 0

대회 중에 7솔을 했는데 정작 재밌어보이는 가운데 3 문제를 제대로 안 잡아봐서 아쉬움이 남네요. 중간에 약속 있어서 ㅌㅌ해서요. 문제 올라오는 대로 F, G, H번 풀어봐야 겠어요.

7cea8173b08469f33cec84e44f9f3433145f551dda4216f03d14d4b9

7cea8173b08468ff3fe98eec439f34337920a5835185b1977f2b2d8d

문제 올라오면 더 정리해볼게요.

A번(학식 사주기) : 간단한 입출력 문제에요. 각 메뉴별 가격을 입력 받아서 배열로 저장해놓은 다음에 학생들이 원하는 메뉴의 각격을 배열에서 찾아서 누적해주면 되네요.

풀이 :

# include <bits/stdc++.h>

using namespace std;

int n, m, b, A[11];

int main(void){

cin >> n;

for(int i=1;i<=n;i++){

cin >> A[i];

}

int answer = 0;

cin >> m;

for(int i=1;i<=m;i++){

cin >> b;

answer += A[b];

}

cout << answer;

}

B번(재수강) : 그냥 substr method를 사용해서 첫 다섯 글자가 같은 얘뜰을 쭉 세주면 되는 간단한 문자열 문제였어요.

풀이 :

# include <bits/stdc++.h>

using namespace std;

string s, t;

int n;

int main(void){

cin >> t >> n;

int answer = 0;

for(int i=1;i<=n;i++){

cin >> s;

if(s.substr(0, 5) == t.substr(0, 5)) answer++;

}

cout << answer;

}

C번(악질 검거) : 그냥 for문으로 입력 받은 문자열을 쭉 훑으면서 연속해서 나온 '.'의 개수를 세주면 되었어요.

풀이 :

# include <bits/stdc++.h>

using namespace std;

int n, m;

char c;

string name;

vector <int> cv;

vector < pair <int, string> > v;

int main(void){

cin >> n >> m;

for(int i=0;i<n;i++){

int tmp = 0, mx = 0;

for(int j=0;j<m;j++){

cin >> c;

if(c == '*'){

mx = max(mx, tmp);

tmp = 0;

continue;

}

tmp++;

}

mx = max(mx, tmp);

cin >> name;

cv.push_back(mx);

v.push_back({mx, name});

}

sort(cv.begin(), cv.end());

cv.erase(unique(cv.begin(), cv.end()), cv.end());

cout << cv.size() << "\n";

for(auto p : v) cout << p.first << " " << p.second << "\n";

}

D번(근로 장학생) : 이것도 문자열 문제였네요. 뭔가 시작 문제들이 거의 다 문자열이라서 신기했어요. vector 자료 구조를 이용해서 (Q, A) 쌍을 정렬한 다음에 for문을 사용해서 문자열을 훑으면서 substr method로 해당 차례의 Q가 들어갈 수 있는지 확인해주면 되요.

풀이 :

# include <bits/stdc++.h>

using namespace std;

int n, m;

string Q, A;

vector < pair <string, string> > v;

string sentence;

int main(void){

cin >> n >> m;

for(int i=0;i<n;i++){

cin >> Q >> A;

v.push_back({Q, A});

}

sort(v.begin(), v.end());

for(int i=0;i<m;i++){

cin >> sentence;

string answer = "";

for(int j=0;j<sentence.size();j++){

int flag = 0;

for(auto [Q, A] : v){

if(j + Q.size() > sentence.size()) continue;

if(sentence.substr(j, Q.size()) == Q){

flag = 1;

answer += A;

}

cout << (answer == "" ? "-1" : answer) << "\n";

}

E번/J번(알파벳과 쿼리) : 논란이 많았던 문제네요. 확실히 풀면서 어디선가 풀어봤던 문제인 것 같다고 느꼈었는데 흐즈로컵에 같은 문제가 있었군요. 구간의 양끝 알파벳과 서로 다른 문자열의 개수를 저장해주면서 세그먼트 트리를 돌리면 되는 문제였어요. 저는 lazy propagation을 사용해서 2번 쿼리를 처리해줬어요.

풀이 :

# include <bits/stdc++.h>

using namespace std;

struct Node{

char lt, rt;

int cnt;

};

int n, q, which, l, r;

string str;

struct Node tree[202020<<2];

int lazy[202020<<2];

void combine_node(struct Node <, struct Node &rt, struct Node &res){

res.lt = lt.lt == '!' ? rt.lt : lt.lt;

res.rt = rt.rt == '!' ? lt.rt : rt.rt;

res.cnt = lt.cnt + rt.cnt - (lt.rt == rt.lt);

}

void init(int s, int e, int node){

if(s == e){

tree[node].lt = str[s];

tree[node].rt = str[s];

tree[node].cnt = 1;

return;

}

int mid = (s + e)/2;

init(s, mid, 2*node);

init(mid + 1, e, 2*node + 1);

combine_node(tree[2*node], tree[2*node + 1], tree[node]);

}

void propagate(int s, int e, int node){

if(!lazy[node]) return;

tree[node].lt = (tree[node].lt - 'A' + lazy[node])%26 + 'A';

tree[node].rt = (tree[node].rt - 'A' + lazy[node])%26 + 'A';

if(s != e){

lazy[2*node] += lazy[node];

lazy[2*node + 1] += lazy[node];

}

lazy[node] = 0;

}

void update(int s, int e, int l, int r, int node){

propagate(s, e, node);

if(l > e || r < s) return;

if(l <= s && r >= e){

lazy[node]++;

propagate(s, e, node);

return;

}

int mid = (s + e)/2;

update(s, mid, l, r, 2*node);

update(mid + 1, e, l, r, 2*node + 1);

combine_node(tree[2*node], tree[2*node + 1], tree[node]);

}

struct Node query(int s, int e, int l, int r, int node){

propagate(s, e, node);

if(l > e || r < s) return {'!', '!', 0};

if(l <= s && r >= e) return tree[node];

int mid = (s + e)/2;

auto lt = query(s, mid, l, r, 2*node);

auto rt = query(mid + 1, e, l, r, 2*node + 1);

struct Node res;

combine_node(lt, rt, res);

return res;

}

int main(void){

ios_base :: sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

cin >> n >> q >> str;

init(0, str.size() - 1, 1);

while(q--){

cin >> which >> l >> r;

l--;

r--;

if(which == 1){

auto res = query(0, str.size() - 1, l, r, 1);

cout << res.cnt << "\n";

}

else{

update(0, str.size() -1, l, r, 1);

}

I번(첫 차 타기) : 다익스트라 알고리즘 문제였고 인접 리스트를 인도와 차도 두 개로 나눠서 관리해줬어요. 차도에 있는 인접 리스트를 이용할 때는 max(현재 시간, k)에서부터 버스를 이용할 수 있다고 처리해주면 해결되어요.

풀이 :

# include <bits/stdc++.h>

# define int int64_t

using namespace std;

const int INF = 1e18 + 7;

int n, k, x, y, u, v, w, dist[202020];

vector < pair <int, int> > adj1[202020], adj2[202020];

priority_queue < pair <int, int>, vector < pair <int, int> >, greater < pair <int, int> > > pq;

int32_t main(void){

cin >> n >> k >> x >> y;

for(int i=1;i<=n;i++){

dist[i] = INF;

}

for(int i=0;i<x;i++){

cin >> u >> v >> w;

adj1[u].push_back({v, w});

adj1[v].push_back({u, w});

}

for(int i=0;i<y;i++){

cin >> u >> v >> w;

adj2[u].push_back({v, w});

adj2[v].push_back({u, w});

}

dist[1] = 0;

pq.push({0, 1});

while(!pq.empty()){

auto [d, cur] = pq.top(); pq.pop();

if(d != dist[cur]) continue;

for(auto [nxt, w] : adj1[cur]){

if(d + w < dist[nxt]){

dist[nxt] = d + w;

pq.push({dist[nxt], nxt});

}

for(auto [nxt, w] : adj2[cur]){

if(max(d, k) + w < dist[nxt]){

dist[nxt] = max(d, k) + w;

pq.push({dist[nxt], nxt});

}

cout << dist[n];

}

구냥 심심한 아침인가보네요:)

- dc official App

고정닉 2

원본 첨부파일 2본문 이미지 다운로드

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	말머리	제목	글쓴이	작성일	조회	추천
2863	설문	시세차익 부러워 부동산 보는 눈 배우고 싶은 스타는?	운영자	24/05/27	-	-
44906	공지	피갤컵 call for tasks를 진행합니다! [7]	*나는최고*	24.05.22	604	16
44466	공지	[ps 정보글 모음집] [2]	*나는최고*	24.05.07	689	12
44058	공지	알고리즘 대회 공부 과정 [22]	*나는최고*	24.04.20	2220	31
19170	공지	규칙 v2022.02.16 [8]	*0xrgb*	22.02.06	6763	36
1	공지	와 PS! [24]	*0xrgb*	18.05.28	21777	30
45036	일반	플레이상한테 질문 [3]	ㅇㅇ(221.161)	01:34	97	0
45035	일반	어제 B GPT로 뚫렸나보네 [8]	ㅇㅇ(211.217)	00:02	229	0
45034	일반	아랫글 보고 올려보는 비재귀 하노이 [1]	ㅇㅇ(125.130)	05.27	126	1
45033	일반	이런 쓰벌 [3]	ㅇㅇ(123.214)	05.27	166	4
45031	일반	일본엔 유독 좆고수 중딩들 많더라 [3]	ㅇㅇ(106.101)	05.27	185	0
45030	일반	여기갤이 디씨에서 학력 평균 젤 높겠지?? [11]	ㅇㅇ(211.234)	05.27	311	0
45029	일반	감사하단말의 진정한 의미 추측.. [2]	ㅇㅇ(106.101)	05.27	255	3
45028	일반	이건 좀 [2]	ㅇㅇ(211.114)	05.27	143	0
45027	일반	치터 떡밥이 끊이질 않아 [1]	ㅇㅇ(223.39)	05.27	157	0
45026	일반	중딩 이하 + 티어 높거나 어려운 문제 자주 품 + CP 안 함 = 치터 [2]	ㅇㅇ(185.217)	05.27	383	10
45025	일반	골드문제 아다 땠다 [1]	ㅇㅇ(123.214)	05.27	131	2
45024	일반	솔브닥 다이아인데 자구알고 과외 주 2회 2시간 [6]	ㅇㅇ(118.235)	05.27	293	0
45023	일반	SCSC 호감이면 개추 ㅋㅋ [1]	ㅇㅇ(221.148)	05.27	229	3
45022	일반	애초에 레이팅 없는거 풀어봐야 정지 먹나 싶은데 [3]	ㅇㅇ(112.217)	05.27	259	2
45021	일반	gpt로 d가 풀리는구나 [2]	ㅇㅇ(113.59)	05.27	280	0
45020	일반	이거도 챗지피티인가 [12]	ㅇㅇ(115.136)	05.27	661	14
45018	일반	그래프 간선 저장방식 [4]	ㅇㅇ(118.235)	05.27	164	0
45017	일반	아호 코라식 이새끼 혁명이네 [3]	ㅇㅇ(106.101)	05.27	242	3
45016	일반	이 문제보고 트라이 떠올리는 미친놈 있음?? [13]	ㅇㅇ(182.225)	05.27	412	1
45015	일반	음수 가중치를 가진 간선이 최대 1~2개인 경우에 최단거리 [2]	ㅇㅇ(118.235)	05.27	165	0
45014	일반	뉴비 깃허브 백준허브 질문점 [1]	ㅇㅇ(112.152)	05.27	219	0
45013	일반	솔브닷 다이아 이상 찍은 사람들 중에서 [12]	ㅇㅇ(14.52)	05.27	529	0
45012	풀이	예 D번 제 풀?이	EN_SA	05.27	252	9
45011	일반	증명 못하면 구현 안 하는 병 어떻게 고침 [11]	ㅇㅇ(49.165)	05.27	330	0
45010	일반	댓글보니까 E는 ioi문제랑 비슷하다네 [2]	ㅇㅇ(182.231)	05.27	162	0
45009	일기	아오코포시치해싱억까그렇게해놓구정해를해싱으로놔 [3]	EN_SA	05.27	221	0
45008	일반	어제랑 오늘 합쳐서 130떨궜다	ㅇㅇ(106.102)	05.27	96	0
45007	일기	터질삘인데 [23]	EN_SA	05.27	447	0
45005	일기	오늘자 div.2	ㅇㅇ(182.231)	05.27	99	0
45003	일반	오늘 몇시까지 문제풀건가요?	ㅇㅇ(221.145)	05.27	100	0
45002	일반	G 왜틀리는거냐 [2]	ㅇㅇ(119.194)	05.26	191	0
45000	일반	오픈콘 아쉽다	ㅇㅇ(182.231)	05.26	162	0
44999	일반	다항시간에 문제 푸는 놈들 특: 인생 시간 낭비 중ㅋㅋ [7]	ㅇㅇ(218.147)	05.26	602	25
44998	일반	걍 동네 학교 대회나 취업용 코테는 파이썬 억까 상관없음? [6]	ㅇㅇ(211.213)	05.26	292	0
44997	일반	파이썬특) [2]	ㅇㅇ(82.102)	05.26	182	1
44996	일반	파이썬<<GOAT [3]	물감비	05.26	345	3
44995	일반	이분매칭 왜 이렇게 어려워? [4]	ㅇㅇ(220.76)	05.26	323	0
44993	일반	백준 메모리 제한 빡세면 파이썬 못쓰더라 [2]	ㅇㅇ(121.55)	05.26	293	0
44992	일반	파이썬에서 c++로 갈아탄 이유 [4]	ㅇㅇ(39.7)	05.26	293	0
44991	일기	진짜 왜 나는 문제를 다시 읽어볼 생각을 안하는걸까	ㅇㅇ(223.39)	05.26	152	0
44990	일반	요즘왜케 병신들이 늘어남? [9]	ㅇㅇ(106.101)	05.26	689	15
44989	일반	ABC 치고 자고 일어나서 프로필 봤는데 슬퍼진다 [1]	ㅇㅇ(59.29)	05.26	217	1
44987	일기	d번까지 1시간컷 내고 싱글벙글했는데	ㅇㅇ(211.234)	05.26	169	0
44986	일반	f같은거 잘풀려면 어케해야되지	ㅇㅇ(182.231)	05.26	87	0
44985	일반	왜 반환타입 void를 int로 바꾸면 TLE 뜸? [3]	ㅇㅇ(220.120)	05.26	251	0
44984	일반	혹시 지금 BOJ Random Defense 설치됨?? [3]	dpk	05.26	278	0
44983	일반	파이썬 TLE떠서 필사의각오로 C++공부했는데 [2]	dpk	05.26	243	0
44982	일반	E HLD 썻다는 사람들 nlog^2n 맞지? [5]	ㅇㅇ	05.26	220	0
44981	일반	예상점수등락 보니까 마음아프다 [2]	ㅇㅇ(211.217)	05.26	181	0
44980	일기	E화나네 왜틀리지 [2]	EN_SA	05.26	152	1