대회 링크
안타깝게도 C++이므로 python 유저분들은 풀이만 슬쩍 봐주시면 될 듯 합니다.
잡설
원래 1시간 48분 차에 4솔을 해서 "한 자리수 가즈아ㅏ" 이러고 있었는데요,
없었습니다.
변수명 m 겹쳐서 디버깅 눈 빠지게 하다가 3시간 15분 차에 올솔하고 12등 됐네요.
아 그리고 그것도 문제에요. 3번 문제에서 값 전달이 아니라 주소 전달을 해버려서 다 참조하고 도는거 찾아내느라 그것도 눈 빠졌어요.
여러모로 바보같은 짓을 많이 했네요.
어떻게 올솔인데 12등이 되는거죠?
하여튼 풀이 시작합니다.
진짜 매크로 요맨큼만요
#include <bits/stdc++.h>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define SZ(x) (int)(x).size()
using namespace std;
using ll = long long;
using ii = pair<int,int>;
void solution(); int main() {ios::sync_with_stdio(0); cin.tie(0); solution();}이 정도는 이해해주실 수 있으시죠?ㅠㅠ
아 그리고
input() 함수를 따로 빼놓고 푸는 편인데, 보기 거슬리니까 생략했습니다.
full 코드 원하시면 비댓으로든 뭐든 알려주시면 드립니다.
아 걍 깃헙에 올릴까요? 일단 풀이 적고 있으니까 나중에 올리도록 할게요.
1 - 빌런 호석
구현이 꽤 어려운 문제입니다. 사실상 2번, 4번보다 어려운 문제였지요. (아님말고)
요약
주어진 수 속 디지털 숫자들을 다른 숫자로 바꾸는데,
몇가지 조건을 만족하게 바꾸는 방법을 세시오.
접근
- 숫자들의 고유한 LED 상태만 기록해두고서 LED 상태가 얼마나 다른지를 구현을 통해 찾아낸 후 풀이 시작
- 직접 숫자들 간에 얼마나 다른지 다 적어두고(약 40개, 나머지 절반은 코드로 정확히 대칭 시키면 됨) 풀이 시작.
| 1번 | 2번 | |
|---|---|---|
| 장점 | 성공하면 괜히 기분 좋음 | 구현 안 해도 됨 ㅎ |
| 단점 | 구현 짜증나 | 삐끗하면 망할 수 있음 |
네 그렇습니다. 전 삐끗했다가 실수한 부분이 0->2 자리라서 운 좋게 빨리 고치고 넘어갔지만, 38번째 막 이런 곳에서 실수했으면 골로 가는 겁니다.
풀이
이므로 다 돌면서 확인하면 됩니다.
의 각 에 대해 적당한 판별 함수를 만들면 구현하기 편할 겁니다.
이런 문제에서 유용한 라이브러리 함수는 to_string, stoi 이런게 있으니 알아두시면 좋을 것 같네요.
코드
const int N = 1000003;
int cnt = 0;
int dist[10][10] = {
{0,4,3,3,4,3,2,3,1,2},
{0,0,5,3,2,5,6,1,5,4},
{0,0,0,2,5,4,3,4,2,3},
{0,0,0,0,3,2,3,2,2,1},
{0,0,0,0,0,3,4,3,3,2},
{0,0,0,0,0,0,1,4,2,1},
{0,0,0,0,0,0,0,5,1,2},
{0,0,0,0,0,0,0,0,4,3},
{0,0,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0},
};
int n, k, p, x;
string s;딱 준비 자세입니다.
전 앞서 말했듯이 dist[10][10]를 노가다로 채우고 시작했습니다.
void input() {
REP(i,0,9) REP(j,0,i-1)
dist[i][j] = dist[j][i];
cin >> n >> k >> p >> x;
s = to_string(x);
while (SZ(s) < k) s = "0"+s;
}
void solution() {
input();
REP(i,1,n) {
if (i == x) continue;
string tar = to_string(i);
while (SZ(tar) < k) tar = "0"+tar;
if (d(s,tar) <= p) ++cnt;
}
cout << cnt;
}위에서 말했다시피 으로 다 돌면서 확인합니다.
와중에 자릿수 맞출라고 앞에다 0 좀 끼워넣는것도 잊지 마세요.
d(x,y)는 두 수 간에 반전해야 하는 LED를 계산해주는 함수입니다.
int d(string x, string y) {
int ret = 0;
REP(i,0,k-1) ret += dist[x[i]-'0'][y[i]-'0'];
return ret;
}2 - 정보 상인 호석
이 문제는 코테특을 잘 보여주는 문제입니다.
자료구조를 잘 쓸 수 있냐죠.
자료구조 사용법만 확실히 잡아뒀으면 구현은 매우 쉽습니다.
요약
정보가 있다는 사실을 입수하는 쿼리랑 정보를 구매하는 쿼리를 쭉 진행한 후, 내가 쓴 총 비용을 출력하시오.
접근
아, 일단 이름이 들어오네... map!
가치가 큰 정보들부터 사들이네... 항상 가장 큰 놈들로?
어? 그럼 매 순간 가장 큰 놈들만 가져다 주면 되는거잖아?
heap이구만!
풀이
접곧풀.
map에서 유용한 함수 하나 짚고 넘어갈게요.
m.count(x): m에 x가 몇 개 존재하는가?
코드
map<string,priority_queue<int>> m;
void solution() {
int q; cin >> q;
ll cnt = 0;
REP(i,1,q) {
int com; cin >> com;
if (com == 1) {
int k; string s; cin >> s >> k;
REP(j,1,k) {
int c;
cin >> c;
m[s].push(c);
}
} else {
string s; cin >> s;
int b; cin >> b;
if (!m.count(s)) continue;
REP(j,1,b) {
if (empty(m[s])) break;
cnt += m[s].top();
m[s].pop();
}
}
}
cout << cnt;
}3 - 트리 디자이너 호석
어쩌다 보니 오늘의 킬러 문항...
요약
한 경로 위에서 숫자들이 단조증가하도록 전구들을 켜는 방법의 수를 구하시오.
접근
우선 LIS를 떠올린 분들도 계실테고요... 근데 그렇게 해서 푸셨나요..? ㅋㅋㅋ
저도 떠올렸는데 별달리 수가 없어서 방법을 바꿨습니다.
이네요? 가 붙을법도 하지만, 트리 문제에서 붙으면 확 어려워져서 코테에 나옴직(?)하지 않아요.
그러면 의 tree DP 정도가 가장 풀이일 법 합니다.
tree DP는 인자로 들어갈 만한 요소가 어느정도 전형적이라 해볼만 합니다.
그럼 풀이로 가시죠.
풀이
문제의 키포인트는 이거에요. 각 전구의 값이 0~9 사이 숫자라는거죠.
저도 이걸 보기 전에는 막막했습니다. 이거 지나쳐서 못 푸신 분들은 다시 풀어보세요.
가 단조증가수열의 끝 숫자인 단조증가수열의 개수
이 DP 테이블을 dfs로 들고 다닐 겁니다.
코드
const int N = 100003, MOD = 1'000'000'007;
int n, val[N];
vector<int> adj[N];adj[N]은 인접리스트로, 그래프를 나타냅니다.
void solution() {
input();
cout << dfs({0,0,0,0,0,0,0,0,0,0});
}최초의 DP 테이블은 전부 0으로 초기화하고 들어가야 할 겁니다.
ll dfs(vector<ll> v, int s = 1, int e = 0) {
ll cnt = 1;
REP(i,0,val[s])
cnt = (cnt+v[i])%MOD;
v[val[s]] = (v[val[s]]+cnt)%MOD;
for (auto u : adj[s]) {
if (u == e) continue;
cnt = (cnt+dfs(v,u,s))%MOD;
}
return cnt;
}MOD 처리 빼먹지 마시고, 단조증가에서 증가가 아니라 같은 상태에서 DP가 어떻게 처리되는지를 유심히 확인하시기 바랍니다.
질문은 언제나 댓글주세요.
4 - 공정 컨설턴트 호석
이건... 너무 전형적인 문제인데, 처음 접하는 컨셉이면 맞는게 더 이상하지요.
처음 접하신다면 제 풀이 보고 난 뒤 더 공부해보시는 걸 추천드려요.
요약
이미 짧다 ㅋㅋ
접근
공정 라인의 수를 최소화 시키고 싶다.
근데, 공정 라인을 충분히 많이 쓰면 넉넉하게 될텐데... 조금 쓰면 또 안 되고.
그 경계를 빠르게 찾는 방법은 뭐가 좋을까?
풀이
전형적인 parametric search입니다.(최적화 문제를 결정 문제로 바꿔 푸는 기법)
이진탐색의 응용 유형이죠.
https://mathsciforstudent.tistory.com/171 여기에 제가 적어뒀으니 그쪽 댓글로 질문 같은거 남겨주시면 답해드릴게요.
코드
주의! 저는 입력의 x를 ub로 바꿔 표기했습니다.
const int N = 100003;
int n;
ll ub, a[N];ub 확인해주세요.
void solution() {
cin >> n >> ub;
REP(i,1,n) cin >> a[i];
int x = 0;
for (int b = n; b >= 1; b >>= 1)
while (!ok(x+b)) x += b;
cout << x+1;
}이건 제 이진탐색 코드인데, 각자 스타일이 다르니 '아 그렇구나' 하고 넘어가주시면 감사하겠습니다.
bool ok(ll x) {
priority_queue<ll> pq;
REP(i,1,x) pq.push(0);
REP(i,1,n) {
auto tmp = pq.top();
pq.pop();
pq.push(tmp-a[i]);
}
ll cnt = 0;
while (!empty(pq)) {
cnt = max(cnt,-pq.top());
pq.pop();
}
return cnt <= ub;
}얘도 heap을 쓰면 됩니다. 코테가 heap 되게 좋아하던데 꼭 알아두세요.
5 - 호석사우르스
요약
격자에서 최단거리 구해주세요. 다익스트라입니다.
접근
다익스트라라는데 별 수 있나요 시키는대로 해야지.
풀이
다익스트라라고 하네요. 그냥 짜도록 하죠.
코드
제 구현은 좀 유니크해서 꺼려지면 가셔도 좋습니다.
저는 complex<int>를 사용하는데 전 괜찮더라고요. 물론 UB인데 덧셈 정도는 문제 없는거고, 그래도 꺼려지면 별 수 없네요...
using ci = complex<int>;
#define R real()
#define C imag()
#define P(x) (x).R][(x).C전 격자 위에서는 예외적으로 매크로를 더 쓰는 편입니다.
저 혼자 터득한 구현인데 다른 분들 어떻게 구현하시는지 모르겠네요. 암튼 다익스트라입니다.
const int N = 103;
int n, m, w[N][N], dist[N][N][3];
bool processed[N][N][3];
ci s, e;
const vector<ci> d[3] {{{0,1},{1,0},{0,-1},{-1,0}},
{{1,0},{-1,0}},
{{0,1},{0,-1}}};inline bool canGo(ci s) {
return 1 <= s.R && s.R <= n && 1 <= s.C && s.C <= m && w[P(s)] != -1;
}여러모로 저 혼자만 알아볼 수 있는 코드 같네요. 가독성이나 변수명은 괜찮은 것 같은데 매크로가 많아서...ㅠ
void solution() {
input();
priority_queue<tuple<int,ii,int>> pq; pq.push({0,{s.R,s.C},0});
dist[P(s)][0] = 0;
while (!empty(pq)) {
auto [_,tmp,mv0] = pq.top(); pq.pop();
ci a = {tmp.first,tmp.second};
if (processed[P(a)][mv0]) continue;
processed[P(a)][mv0] = true;
int mv = (mv0+1)%3;
for (ci d : d[mv]) {
ci b = a+d;
if (!canGo(b)) continue;
if (dist[P(b)][mv] > dist[P(a)][mv0]+w[P(b)]) {
dist[P(b)][mv] = dist[P(a)][mv0]+w[P(b)];
pq.push({-dist[P(b)][mv],{b.R,b.C},mv});
}
}
}
int ans = min({dist[P(e)][0],dist[P(e)][1],dist[P(e)][2]});
if (ans >= 1000000000) cout << -1;
else cout << ans;
}분명히 어디 설명이 찝찝한 부분이 있으실텐데 망설이지 말고 댓글 달아주세요.
좀 빨리 받고 싶으시면 https://mathsciforstudent.tistory.com/manage/posts 여기에 달아주세요. 앱으로 들어가는거라 바로 답해드릴 수 있어요.
