dcom-khu / 2021-summer-dcomding Goto Github PK
View Code? Open in Web Editor NEW2021 여름방학 디닷컴 코딩테스트 스터디
2021 여름방학 디닷컴 코딩테스트 스터디
정답 : 10명
B = list(map(int, input().split()))
C = [str(sum([B[i] for i in [-1-p-d for p in range(0, 15, 2**(x+1)) for d in range(2**x)][0:7]] + [B[2**x-1]])%2) for x in range(4)]
error = int('0b'+''.join(C[::-1]), base=0)
if error:
B[error-1] = 1 - B[error-1]
print(int('0b'+''.join([str(B[i-1]) for i in range(1, 16) if i not in [2**x for x in range(4)]][::-1]), base=0))
정답 : 13명
stack을 이용한 풀이
def isRight(s):
stack = list()
for ch in s:
for open, close in zip('[({', '])}'):
if ch == open:
stack.append(open)
break
elif ch == close:
if stack and stack[-1] == open:
stack.pop()
break
else:
return False
return False if stack else True
s = input()
print(sum([isRight(s[i:]+s[:i]) for i in range(len(s))]))
정답 : 5명
stack을 이용한 풀이
import sys
from collections import deque
input = sys.stdin.readline
def solution():
n = int(input())
can_go = {}
for i in range(n):
start, end = input().split()
try:
can_go[start].append(end)
except:
can_go[start] = [end]
def custom_rank(key):
'''길이와 사전순을 기준으로 정렬'''
return (len(key), key)
for idx in can_go:
can_go[idx] = deque(sorted(can_go[idx],key = custom_rank))
result = []
# 손선생님의 손길이 탄 코드입니다.
funcStack = deque(["DCOM"])
while funcStack:
cur = funcStack[-1]
try:
funcStack.append(can_go[cur].popleft())
if not can_go[cur]:
del can_go[cur]
except:
result.append(funcStack.pop())
continue
print(*result[::-1])
solution()
정답 : 11명
two pointer 알고리즘을 이용한 풀이
gems=[]
for i in range(int(input())):
gems.append(str(input()))
def solution(gems):
TYPE_NUM=len(set(gems))
GEM_NUM=len(gems)
cur_shop={gems[0]:1}
cand=[]
l_idx,r_idx=0,0
DIST,RESULT=0,1
while l_idx<GEM_NUM and r_idx<GEM_NUM:
if len(cur_shop)<TYPE_NUM:
r_idx+=1
if r_idx==GEM_NUM:
break
cur_shop[gems[r_idx]]=cur_shop.get(gems[r_idx],0)+1
else:
cand.append((r_idx-l_idx,[l_idx+1,r_idx+1]))
cur_shop[gems[l_idx]]-=1
if cur_shop[gems[l_idx]]==0:
del cur_shop[gems[l_idx]]
l_idx+=1
cand=sorted(cand,key=lambda x:(x[DIST],x[RESULT]))
def print_it():
for i in cand[0][RESULT]:
print(i)
return print_it()
solution(gems)
#print(solution(["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]))
#투포인터 알고리즘 사용
#두 포인터를 설정하여 4가지 보석이 존재하지 않으면 end를 증가시키고 4가지 보석이 존재하면 start를 증가시킴
슬라이딩 윈도우 알고리즘을 이용한 풀이
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
int n;
int item_cnt = 0;
int category_cnt;
vector<string> v;
int s_idx = 0;
int e_idx = 0;
map<string, int> m;
set<string> s;
/*
void get_start_window(){
int isFind = false;
int idx = s_idx;
while(!isFind){
m[v[idx]] -= 1;
if(m[v[idx]] == 0){
item_cnt -= 1;
}
if(item_cnt != category_cnt){
m[v[idx]] += 1;
item_cnt += 1;
s_idx = idx;
isFind = true;
}
idx++;
}
}
*/
void get_end_window(){
while(e_idx < n){
//cout << idx << endl;
m[v[e_idx]] += 1;
if(m[v[e_idx]] == 1){
item_cnt += 1;
}
if(item_cnt == category_cnt){
break;
}
e_idx++;
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int s_ans, e_ans, w_size;
bool isBuy = false;
cin >> n;
for(int i = 0; i < n; i++){
string s;
cin >> s;
v.push_back(s);
if(m.find(s) == m.end()){
m.insert({s,0});
}
}
category_cnt = m.size();
//슬라이딩 윈도우의 끝 지점을 찾는다.
get_end_window();
s_ans = s_idx;
e_ans = e_idx;
w_size = e_ans - s_ans;
while(e_idx < n){
//cout << s_idx << " " << e_idx << endl;
string item = v[s_idx];
m[item]--;
s_idx++;
if(m[item] == 0){
item_cnt--;
e_idx++;
get_end_window();
}
if(item_cnt == category_cnt && w_size > e_idx - s_idx){
s_ans = s_idx;
e_ans = e_idx;
w_size = e_ans - s_ans;
}
}
cout << s_ans + 1 << endl << e_ans + 1;
return 0;
}
정답 : 6명
n = int(input(""))
directions = list(map(int, input("").split()))
mov = [(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1)]
new = True
now = (0, 0)
bef = (3, 3)
visited = {now:[-1]}
shapes = 0
additional = False
for d in directions:
nex = (now[0]+mov[d][0], now[1]+mov[d][1])
if d%2 == 1:
try:
if (d+2)%8 in visited[(now[0]+mov[(d+1)%8][0]) ,(now[1]+mov[(d+1)%8][1]) ]:
additional = True
except:
additional = False
if nex in visited:
if d not in visited[nex]:
shapes += 1
if additional:
shapes += 1
additional = False
visited[nex].append(d)
visited[now].append((d+4) % 8)
else:
additional = False
new = False
else:
visited[nex] = [d]
visited[now].append((d+4) % 8)
new = True
if additional:
shapes += 1
additional = False
bef = now
now = nex
# if d == 0:
# nex = (now[0], now[1]+1)
# elif d == 1:
# nex = (now[0]+1, now[1]+1)
# try:
# if 7 in visited[(now[0]), now[1]+1] or 3 in visited[(now[0]+1, now[1])]:
# additional = True
# else:
# additional = False
# except:
# additional = False
# elif d == 2:
# nex = (now[0]+1, now[1])
# elif d == 3:
# nex = (now[0]+1, now[1]-1)
# try:
# if 5 in visited[(now[0], now[1]-1)] or 1 in visited[(now[0]+1, now[1])]:
# additional = True
# else:
# additional = False
# except:
# additional = False
# elif d == 4:
# nex = (now[0], now[1]-1)
# elif d == 5:
# nex = (now[0]-1, now[1]-1)
# try:
# if 7 in visited[(now[0]-1, now[1])] or 3 in visited[(now[0], now[1]-1)]:
# additional = True
# else:
# additional = False
# except:
# additional = False
# elif d == 6:
# nex = (now[0]-1, now[1])
# elif d == 7:
# nex = (now[0]-1, now[1]+1)
# try:
# if 5 in visited[(now[0]-1, now[1])] or 1 in visited[(now[0], now[1]+1)]:
# additional = True
# else:
# additional = False
# except:
# additional = False
# if nex in visited:
# if nex != bef and d not in visited[nex]:
# shapes += 1
# if additional:
# shapes += 1
# additional = False
# visited[nex].append(d)
# else:
# additional = False
# new = False
# else:
# visited[nex] = [d]
# visited[now].append((d+4) % 8)
# new = True
# if additional:
# shapes += 1
# additional = False
# bef = now
# now = nex
print(shapes)
1주차 후반부터 실행 시간을 기록하도록 시스템이 개선되어 2주차부터는 모범 답안 선정시에도 실행 시간을 고려하고 있습니다. 모범 답안은 실행 시간
, 최적화 정도
, 가독성
등을 종합적으로 검토하여 선정하며,
비슷한 경우 모범 답안 선정 횟수가 적은 분을 우선으로 선정합니다.
모범 답안 작성 후 해설 작성시 모범 답안 채택 갯수 시상
에 우대합니다(동점자 발생시). 모범 답안 선정되신 분들은 다른 학우분들이 코드를 보고 공부하실 수 있도록 해설 남겨주시면 감사드리겠습니다.
코드에 주석으로 달아주신 분들은 해설을 작성해주신것으로 간주하겠습니다. 물론 추가 해설을 작성해주시면 너무 감사드립니다.
해설은 본 이슈에 계속 달아주세요!
모범 답안 및 해설에 대한 질문이 있으신 분들도 여기에 같이 남겨주시면 좋을 것 같습니다. 슬랙 #dcomding 채널을 이용해주셔도 좋습니다.
정답 : 10명
import math
n = int(input())
# 1 -> 1
# 1 2 -> 2
# 1 2 3 -> 2
# 1 2 3 4 -> 2 4 -> 4
# 1 2 3 4 5 -> 2 4 -> 4
# 1 2 3 4 5 6 -> 2 4 6 -> 4
# 1 2 3 4 5 6 7 -> 2 4 6 -> 4
# 1 2 3 4 5 6 7 8 -> 2 4 6 8 -> 4 8 -> 8
# ...
# 1 2 3 ... n -> ... -> 2 ^ floor(log_2(n))
print(2 ** int(math.log2(n)))
정답 : 10명
a, b = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
count, i = 0, 0
for an in A:
while i < b and B[i] <= an:
if B[i] == an:
count += 1
i += 1
print(a + b - 2*count)
정답 : 7명
dfs + dp를 이용한 풀이
#include <iostream>
#include <set>
using namespace std;
int slope[502][502];
int cases[502][502];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
int M, N;
bool is_available(int x, int y, int i) {
bool res = false;
if (x + dir[i][0] > 0 && x + dir[i][0] <= M && y + dir[i][1] > 0 && y + dir[i][1] <= N) {
res = true;
}
return res;
}
int getload(int x, int y) {
int res = 0;
bool found = false;
//cout << "x: " << x << ", y: " << y << "\n";
if (cases[x][y] != -1) {
//cout << cases[x][y] << "\n";
return cases[x][y];
}
if (x == M && y == N) {
return 1;
}
for (int i = 0; i < 4; i++) {
if (is_available(x, y, i)) {
if (slope[x][y] > slope[x + dir[i][0]][y + dir[i][1]]) {
res += getload (x + dir[i][0], y + dir[i][1]);
}
}
}
//cout << res << "\n";
cases[x][y] = res;
return res;
}
int main() {
cin >> M >> N;
for (int i = 1; i <= M;i++) {
for (int j = 1; j <= N; j++) {
cin >> slope[i][j];
cases[i][j] = -1;
}
}
cout << getload(1, 1);
}
정답 : 3명
bfs를 이용한 풀이
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define pii pair<int, int>
#define abs(a) (a>0?a:-a)
int n, weights[200000], a, b, res;
bool visited[200000]={1};
vector<vector<int>> tree(200000, vector<int>());
queue<int> bfsQueue;
stack<pii> calcEdges;
int main()
{
scanf("%d",&n);
for(int cnt=0; cnt<n; ++cnt)
scanf("%d",&weights[cnt]);
for(int cnt=1; cnt<n; ++cnt){
scanf("%d%d",&a,&b);
tree[a].push_back(b);
tree[b].push_back(a);
}
bfsQueue.push(0);
while(!bfsQueue.empty()){
int node = bfsQueue.front(); bfsQueue.pop();
for(int cnt=0; cnt<tree[node].size(); ++cnt){
int nextNode = tree[node][cnt];
if(!visited[nextNode]){
++visited[nextNode];
bfsQueue.push(nextNode);
calcEdges.push(make_pair(node, nextNode));
}
}
}
while(!calcEdges.empty()){
int pNode =calcEdges.top().first, cNode = calcEdges.top().second;
calcEdges.pop();
res += abs(weights[cNode]), weights[pNode] += weights[cNode];
}
printf("%d", weights[0]?-1:res);
return 0;
}
정답 : 3명
Priority Queue를 이용한 풀이
#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct Process {
int PID;
long long int ExecTime;
bool operator<(Process _other) const {
if (this->ExecTime == _other.ExecTime) {
return this->PID > _other.PID;
}
else return this->ExecTime > _other.ExecTime;
}
};
class RR {
private:
priority_queue<Process> Table;
vector<int>run;
vector<int>remainTime;
long long curTime=0;
int totallen;
int len;
public:
long long int getPID(long long k) {
Process curP;
bool found = false;
long long res;
long long int clear_iter, prev_iter = 0;
while (true) {
curP = Table.top();
clear_iter = curP.ExecTime;
if (curTime + (clear_iter - prev_iter) * len > k)
break;
else curTime += (clear_iter - prev_iter) * len;
Table.pop();
len--;
prev_iter = clear_iter;
}
vector<int>remain;
while (!Table.empty()) {
curP = Table.top();
Table.pop();
remain.push_back(curP.PID);
}
sort(remain.begin(), remain.end());
res = remain[(k - curTime) % remain.size()];
return res;
}
void getTimes_io() {
int n, timeInput;
long long k,sum = 0;
cin >> n >> k;
len = n;
totallen = n;
for (int i = 0; i < n; i++) {
Process pInput;
cin >> timeInput;
pInput.PID = i;
pInput.ExecTime = timeInput;
sum += timeInput;
Table.push(pInput);
run.push_back(i);
remainTime.push_back(timeInput);
}
if (sum <= k) {
cout << -1;
}
else
cout << getPID(k);
}
};
int main() {
RR table;
table.getTimes_io();
}
제출한 답안 중에는 없었지만 5번은 이외에도 완전히 다른 풀이가 가능합니다.
모범 답안 작성 후 해설 작성시 모범 답안 채택 갯수 시상
에 우대합니다(동점자 발생시). 모범 답안 선정되신 분들은 다른 학우분들이 코드를 보고 공부하실 수 있도록 해설 남겨주시면 감사드리겠습니다.
코드에 주석으로 달아주신 분들은 해설을 작성해주신것으로 간주하겠습니다. 물론 추가 해설을 작성해주시면 너무 감사드립니다.
해설은 본 이슈에 계속 달아주세요!
모범 답안 및 해설에 대한 질문이 있으신 분들도 여기에 같이 남겨주시면 좋을 것 같습니다. 슬랙 #dcomding 채널을 이용해주셔도 좋습니다.
정답 : 13명
counting을 이용한 풀이
#include <cstdio>
#include <algorithm>
using namespace std;
int cardCnt[100001], minPoint=100001, maxPoint, n, k, cardNum, sum;
int main(){
scanf("%d%d",&n,&k);
for(int cnt=0;cnt<n;++cnt){
scanf("%d", &cardNum);
++cardCnt[cardNum];
minPoint = min(minPoint, cardNum);
maxPoint = max(maxPoint, cardNum);
sum+=cardNum;
}
for(int cnt=1;cnt<=k;++cnt){
if(cnt&1){
while(!cardCnt[minPoint]) ++minPoint;
sum-=minPoint;
--cardCnt[minPoint];
}
else{
while(!cardCnt[maxPoint]) --maxPoint;
sum-=maxPoint;
--cardCnt[maxPoint];
}
}
printf("%d",sum);
return 0;
}
정렬을 이용한 풀이
# 숫자 카드 게임 ㅎㅅㅎ
length, numOfTurns = map(int, input().split())
cards = sorted([int(card) for card in input().split()])
# 굳이 이렇게 반복문을 돌릴 필요 없이
# for i in range(1, numOfTurns + 1):
# if i % 2 == 1:
# cards = cards[1:]
# else:
# cards = cards[:-1]
# 생각해보면 그냥 짤릴 앞 뒤는 정해져있으니
cards = cards[(numOfTurns+1)//2:length - numOfTurns//2]
print(sum(cards))
# print(cards)
정답 : 14명
일반항을 계산한 풀이
#include <cstdio>
unsigned long long result=1;
int n;
//1 <= n <= 62 계산 가능
//식은.. 원반이 처음에 위치한 자리에 따리 거쳐가는 막대의 경로가 같기 때문에
//그것을 이용한 O(1)의 일반향입니다.. f(n) = n + 2^(n+1) - 2
int main() {
scanf("%d",&n);
result<<=n+1;
printf("%llu",n+result-2);
return 0;
}
점화식을 계산한 풀이
def solve():
N = int(input())
# 상태를 3개로 나누자.
# now, sub, main / 시작점, 둘다 아닌 곳, 도착점
moves = [[0,0,0] for i in range(N+1)]
moves[0][2] = 1#[0,0,1]
for i in range(1,N):
[bef_now, bef_sub, bef_main] = moves[i - 1]
# 점화식 성립
moves[i] = [bef_now + bef_sub, bef_main + bef_now, bef_sub + bef_main + 1]
print(sum([(i+1) * moves[N-1][i] for i in range(3)]))
solve()
재귀를 이용한 풀이
def hanoi(f, t, n):
return t if n==1 else hanoi(f, 6-f-t, n-1) + t + hanoi(6-f-t, t, n-1)
print(hanoi(1, 3, int(input())))
정답 : 12명
permutation을 이용한 풀이
import itertools
def cal(h, o):
res = nums[0]
for i in range(0,len(o)):
if o[i] == '0':
res += nums[i+1]
elif o[i] == '1':
res -= nums[i+1]
elif o[i] == '2':
res *= nums[i+1]
elif o[i] == '3':
if res < 0:
res = -((-res)//nums[i+1])
else:
res = res//nums[i+1]
h.append(res)
n = int(input())
nums = list(map(int, input().split()))
ops = list(map(int, input().split()))
perm = []
for i in range(0, 4):
for j in range(0, ops[i]):
perm.append(str(i))
perm = list(map(''.join, itertools.permutations(perm, len(perm))))
history = []
perm_set = set(perm)
perm = list(perm_set)
for i in range(len(perm)):
cal(history, perm[i])
print(max(history))
print(min(history))
브루트포싱을 이용한 풀이
maxi, mini = -10**9, 10**9
def fn(num, i, a, b, c, d):
if a+b+c+d:
if a:
fn(num+arr[i], i+1, a-1, b, c, d)
if b:
fn(num-arr[i], i+1, a, b-1, c, d)
if c:
fn(num*arr[i], i+1, a, b, c-1, d)
if d:
fn(int(num/arr[i]), i+1, a, b, c, d-1)
else:
global maxi, mini
maxi, mini = max(maxi, num), min(mini, num)
n = int(input())
arr = list(map(int, input().split()))
fn(arr[0], 1, *map(int, input().split()))
print(maxi)
print(mini)
정답 : 8명
binary search를 이용한 풀이
n, k = map(int, input().split())
stones = list(map(int, input().split()))
# if k == 1, success member is min(stones)
# if k == n, success member is max(stones)
left = min(stones)
right = max(stones)
count = 0
member = right
# binary search
while left <= right:
mid = (left + right) // 2
count = 0
valid = True
# check mid member
for stone in stones:
# if stone < member, stone will be zero before passing
if stone < mid:
count += 1
else:
count = 0
# fail : if k zeros in a row, you should jump k+1
# should check less member
if count >= k:
valid = False
right = mid-1
break
# success
# should check more member
if valid == True:
member = mid
left = mid+1
print(member)
세그먼트 트리를 이용한 풀이
#include <cstdio>
#include <algorithm>
using namespace std;
#define INT_MAX (1<<31)-1
//n,k,stones는 입력받는 값을 저장할 변수, rangeMaxTree, pnt(=point)는 세그먼트 트리를 구현하기 위한 변수 / <<X는 *(2의 X제곱)과 같음.
int n,k,stones[200020], rangeMaxTree[1<<21], pnt=1;
//세그먼트 트리를 업데이트 하는 함수
void update(int node, int value){
//node에 point를 더해 세그먼트 트리의 리프노드를 향하게 만들고
//리프노드는 구간이 하나니까 max값을 계산하는 대신 값을 그대로 저장함
node += pnt;
rangeMaxTree[node] = value;
//그 뒤로 루트노드까지 노드의 부모노드를 방문해서 max값을 재계산함.
while(node/=2)
rangeMaxTree[node] = max(rangeMaxTree[node*2], rangeMaxTree[node*2+1]);
}
int getRangeMax(int srt, int end){
//구간의 시작과 끝점에 point를 더해 세그먼트 트리의 리프노드를 향하게 만듦 + 초기값 세팅
srt += pnt, end += pnt;
int maxNum = 0;
//리프노드들부터 올라가면서 구간의 max값을 구함.
while(srt<=end){
//start가 홀수일 때 더 이상 합칠 구간이 없으므로 max값에 반영 후 start 한 칸 오른쪽으로 이동
if(srt&1) maxNum = max(maxNum,rangeMaxTree[srt++]);
//end가 짝수일 때 더 이상 합칠 구간이 없으므로 max값에 반영 후 end 한 칸 왼쪽으로 이동
if(!end&1) maxNum = max(maxNum, rangeMaxTree[end--]);
//start와 end 모두 부모노드로 올라감. >>=X는 /=(2의 X제곱)과 같음.
srt>>=1, end>>=1;
}
return maxNum;
}
// 알고리즘
// n번째 징검다리에서 건널 수 있는 최대 인원수 = (n-k~n-1번째 징검다리에서 건널 수 있는 최대 인원수) 와 (n번째 징검다리에서 건널 수 있는 인원수) 중 최솟값
// 이라 생각하고 구현했습니당
// 세그먼트 트리는 이 때 [n-k,n-1] 구간의 최댓값을 빨리 구하려고 만드는 것
int main(){
scanf("%d%d",&n,&k);
for(int cnt=1; cnt<=n; ++cnt)
scanf("%d", &stones[cnt]);
//point가 가리킬 위치를 계산하는 것, 세그먼트 트리를 완전 이진 트리로 만들어서 계산에 용이하도록 만듦
while(pnt<=n) pnt<<=1;
update(0, INT_MAX);//INT_MAX는 #define 참고, 처음(0번째 징검다리 = 지상)에는 무제한으로 건너올 수 있으니까 반영함
for(int dpCnt=1; dpCnt<=n; ++dpCnt){
//maxNum : 구간 중 건널 수 있는 최대 인원수, possibleMember = dpCnt번째 징검다리에서 건널 수 있는 최대 인원수
int maxNum = getRangeMax(max(0,dpCnt-k), dpCnt-1),
possibleMember = min(stones[dpCnt], maxNum);
//다음 계산을 위해 세그먼트 트리에 반영
update(dpCnt, possibleMember);
//한 줄로 바꾸면 아래가 됨
//update(dpCnt, min(getRangeMax(max(0,dpCnt-k),dpCnt-1), stones[dpCnt]));
}
//도착지점에서의 구간 최댓값을 구하면 원하는 결과를 얻을 수 있음
printf("%d",getRangeMax(n-k+1,n));
return 0;
}
정답 : 8명
dp를 이용한 풀이
n = int(input())
money = list(map(int, input().split()))
dp = [0 for i in range(n)] # 처음꺼 포함
dp[0], dp[1] = money[0], money[0]
for i in range(2, n - 1):
dp[i] = max(dp[i - 1], dp[i - 2] + money[i])
dp2 = [0 for i in range(n)] # 끝꺼 포함
dp2[0], dp2[1] = 0, money[1]
for i in range(2, n):
dp2[i] = max(dp2[i - 1], dp2[i - 2] + money[i])
print(max(dp[n - 2], dp2[n - 1]))
모범 답안 작성 후 해설 작성시 모범 답안 채택 갯수 시상
에 우대합니다(동점자 발생시). 모범 답안 선정되신 분들은 다른 학우분들이 코드를 보고 공부하실 수 있도록 해설 남겨주시면 감사드리겠습니다.
코드에 주석으로 달아주신 분들은 해설을 작성해주신것으로 간주하겠습니다. 물론 추가 해설을 작성해주시면 너무 감사드립니다.
해설은 본 이슈에 계속 달아주세요!
모범 답안 및 해설에 대한 질문이 있으신 분들도 여기에 같이 남겨주시면 좋을 것 같습니다. 슬랙 #dcomding 채널을 이용해주셔도 좋습니다.
정답 : 10명
stack을 이용한 풀이
n, m = map(int, input().split())
blocks = list(map(int, input().split()))
sum = 0
count = 0
center = 0
base = 0
# check from last block
while blocks and base-m < center < base+m:
sum += blocks.pop()
count += 1
center = sum / count
try:
base = blocks[-1]
except:
break
if count == n:
print(1)
else:
print(0)
정답 : 7명
doubly linked list를 이용한 풀이
str = list(input())
# double linked list
class Node:
def __init__(self, char=''):
self.char = char
self.next = None
self.prev = None
def add(self, char):
node = Node(char)
node.prev = self
node.next = self.next
if self.next:
self.next.prev = node
self.next = node
def delete(self):
self.prev.next = self.next
if self.next:
self.next.prev = self.prev
del self
head = Node('head')
cursor = head
for c in str:
if c == '<':
if cursor.char != 'head':
cursor = cursor.prev
elif c == '>':
if cursor.next:
cursor = cursor.next
elif c == '-':
if cursor.char != 'head':
temp = cursor
cursor = cursor.prev
temp.delete()
else:
cursor.add(c)
cursor = cursor.next
cursor = head.next
while cursor:
print(cursor.char, end='')
cursor = cursor.next
stack을 이용한 풀이
from collections import deque
left, right = deque(), deque() #stack
for key in input():
try:
if key == '<':
right.appendleft(left.pop())
elif key == '>':
left.append(right.popleft())
elif key == '-':
left.pop()
else:
left.append(key)
except IndexError:
continue
print(''.join(left+right))
정답 : 6명
투 포인터를 이용한 풀이
def solution():
# 2000 * 500은 백만.
N = int(input())
cookies = list(map(int, input().split()))
# i는 경계선으로 i를 꼭 포함해야한다.
result = 0
for i in range(N - 1):
boy = cookies[i]
girl = cookies[i+1]
boy_left = i
girl_right = i + 1
while not (boy_left == 0 and girl_right == N - 1):
if boy == girl:
result = max(boy, result )
if boy_left == 0:
girl_right += 1
girl += cookies[girl_right]
else:
boy_left -= 1
boy += cookies[boy_left]
elif boy > girl:
if girl_right == N- 1:
break
girl_right += 1
girl += cookies[girl_right]
elif boy < girl:
if boy_left == 0:
break
boy_left -= 1
boy += cookies[boy_left]
if boy == girl:
result = max(boy, result )
return result
print(solution())
binary search를 이용한 풀이
#include <cstdio>
#define max(a,b) (a>b?a:b)
//sumCookies : 1~n까지 쿠키의 누적합
int n, cookie, sumCookies[2001], res;
//[a,b], [b+1,c]중 b를 담당하는 이진 탐색
//a,c가 정해져 있으면 각 구간의 합이 동일하게 만드는 b는 여러개라도 동일한 구간의 합의 값은 단 1개이다.
//또한 f(x) = [a,x] - [x+1,c]로 두면 f(x)는 증가함수 이므로 이를 이용해 이진탐색이 가능하다.
int binary_search(int eLeft, int eRight){
//rSum = [1,eRight] - [1,eLeft], 즉, [1,c] - [1,a-1] = [a,c] // mid가 b의 역할을 함
int left = eLeft+1, right = eRight, mid, lSum, rSum = sumCookies[eRight]-sumCookies[eLeft];
while(left<=right){
//lSum = [1,b] - [1,a-1] = [a,b]
mid = (left+right)/2, lSum = sumCookies[mid]-sumCookies[eLeft];
//[a,b] == [b+1,c] ==> [a,b] == [a,c]-[a,b] ==> 2*[a,b] == [a,c]
if(2*lSum == rSum) return lSum;
else if(2*lSum > rSum) right = mid-1;
else left = mid+1;
}
return -1;
}
int main() {
scanf("%d",&n);
//[a,b], [b+1,c]중 c를 담당하는 for문
for(int cnt=1; cnt<=n; ++cnt){
scanf("%d",&cookie);
//값을 입력 받으면서 바로 구간합을 갱신함
sumCookies[cnt] = sumCookies[cnt-1]+cookie;
//[a,b], [b+1,c]중 a를 담당하는 for문, srtBasket == a-1임
for(int srtBasket = 0; srtBasket<cnt; ++srtBasket){
//binary search를 이용해서 구간의 합을 찾고 답을 갱신함
res = max(res, binary_search(srtBasket, cnt));
}
}
printf("%d", res);
return 0;
}
정답 : 4명
dp를 이용한 풀이
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
vector<string> words;
const int MAX = 99999999;
int dp[20005];
int main(){
int n;
string str;
cin >> n;
cin >> str;
for(int i = 0; i < n; i++){
string s;
cin >> s;
words.push_back(s);
}
for(int i = 1; i <= str.length(); i++){
dp[i] = MAX;
}
for(int i = 1; i <= str.length(); i++){
for(int j = 0; j < words.size(); j++){
string s = words[j];
if(i - s.length() < 0){
continue;
}
bool flag = true;
for(int k = 0; k < s.length(); k++){
if(s[k] != str[i - s.length() + k]){
flag = false;
break;
}
}
if(flag){
dp[i] = min(dp[i], dp[i - s.length()] + 1);
}
}
}
int ans = dp[str.length()];
if(ans == MAX){
cout << -1;
}else{
cout << ans;
}
return 0;
}
trie + dp를 이용한 풀이
//Trie + DP로 풀기
#include <cstdio>
#include <cstring>
#define min(a,b) (a<b?a:b)
class Trie{
public:
Trie* abt[26];
bool isEnd; //끝난지점을 확인하기 위해 변수 추가
Trie(){
memset(abt, 0, sizeof(abt));
isEnd=false;
}
~Trie(){
for(int cnt=0; cnt<26; ++cnt)
if(abt[cnt]) delete abt[cnt];
}
Trie* insert(int ch){
if(!abt[ch-='a'])
abt[ch] = new Trie();
return abt[ch];
}
};
//wordDp[n] : n-1번째 문자열을 완성하는데까지 사용한 단어의 최소 개수
int n, wordDp[20010], cnt, len, cur;
char str[20010], word[6];
Trie root;
Trie* trie;
int main(){
scanf("%d",&n); getchar();
scanf("%s", str);
for(cnt=0; cnt<n; ++cnt){
scanf("%s",word);
trie = &root;
//단어를 트라이 자료구조에 넣음
for(cur=0; word[cur]; ++cur)
trie = trie->insert(word[cur]);
//단어의 마지막 알파벳 위치에 단어가 끝났다는 것을 저장함
trie->isEnd = true;
}
//DP 초기값 설정
for(cnt=1; cnt<=20000; ++cnt)
wordDp[cnt] = 1<<30;
for(len=0; str[len]; ++len){
trie = &root, cur=len;
//문자열이 끝나지 않았고 트라이에 str[cur]에 해당하는 알파벳이 없을 때까지 반복
while(str[cur] && (trie = trie->abt[str[cur++]-'a'])){
//단어가 끝났다면 DP값을 갱신함
if(trie->isEnd) wordDp[cur] = min(wordDp[cur], wordDp[len]+1);
}
}
//주어진 단어들로 문자열을 만들 수 없다면 -1, 아니면 dp값을 출력함
printf("%d", wordDp[len]==(1<<30)?-1:wordDp[len]);
return 0;
}
정답 : 2명
dp를 이용한 풀이
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
//dp[n] : n을 루트로 하는 서브 트리에서 ([0] : n을 포함하지 않고, [1] : n을 포함하고) 서브 트리의 모든 팀을 참여시킬 때의 매출액의 최솟값
int n, sales[300001], leader, member, dp[300001][2];
vector<vector<int>> tree(300001,vector<int>());
stack<pair<int, int>> funcStack;
int main(){
scanf("%d",&n);
for(int cnt=0;cnt<n;++cnt)
scanf("%d",&sales[cnt]);
for(int cnt=1;cnt<n;++cnt){
scanf("%d%d",&leader,&member);
tree[leader].push_back(member);
}
//재귀함수 대신 funcStack 사용
funcStack.push(make_pair(0,0));
while(!funcStack.empty()){
int leader = funcStack.top().first, mode = funcStack.top().second;
funcStack.pop();
//mode가 0일 때는 재귀적으로 각 서브 트리로 진입함
if(!mode){
funcStack.push(make_pair(leader,1));
for(int cnt=0;cnt<tree[leader].size();++cnt)
funcStack.push(make_pair(tree[leader][cnt],0));
}
//mode가 1일 때 팀원노드들은 모두 계산이 완료되어 있으므로 팀장노드를 계산함
else{
//팀장 노드가 들어갈 때(dp[leader][1])는 항상 팀장의 팀이 들어가니까
//팀원들이 들어가든 말든 상관없이 (팀원하위팀 매출액 최솟값의 합 + 팀장 매출액) 이 최솟값이 됨
//팀장 노드가 들어가지 않을 때(dp[leader][0])는 팀원 1명 이상이 무조건 들어가 있어야 하니
//sumMembers를 이용해서 예외상황을 처리함
int sumMembers = 0;
for(int cnt=0; cnt<tree[leader].size(); ++cnt){
member = tree[leader][cnt];
dp[leader][0] += min(dp[member][0], dp[member][1]), sumMembers += dp[member][0];
}
dp[leader][1] = dp[leader][0]+sales[leader];
//dp[leader][0]은 현재 (팀원하위팀 매출액 최솟값의 합)이기 때문에 이게 sumMembers이랑 같다는 건
//팀원이 한명도 들어가 있지 않다고 추측할 수 있음
if(tree[leader].size() && dp[leader][0] == sumMembers){
//따라서 팀원을 한 명씩 넣어보면서 최솟값을 갱신함
dp[leader][0] = (1<<31)-1;
for(int cnt=0; cnt<tree[leader].size(); ++cnt){
member = tree[leader][cnt];
dp[leader][0] = min(dp[leader][0], sumMembers-dp[member][0]+dp[member][1]);
}
}
}
}
//CEO가 들어간 최솟값과 제외한 최솟값 중 더 작은 값을 출력함
printf("%d", min(dp[0][0], dp[0][1]));
return 0;
}
모범 답안 작성 후 해설 작성시 모범 답안 채택 갯수 시상
에 우대합니다(동점자 발생시). 모범 답안 선정되신 분들은 다른 학우분들이 코드를 보고 공부하실 수 있도록 해설 남겨주시면 감사드리겠습니다.
코드에 주석으로 달아주신 분들은 해설을 작성해주신것으로 간주하겠습니다. 물론 추가 해설을 작성해주시면 너무 감사드립니다.
해설은 본 이슈에 계속 달아주세요!
모범 답안 및 해설에 대한 질문이 있으신 분들도 여기에 같이 남겨주시면 좋을 것 같습니다. 슬랙 #dcomding 채널을 이용해주셔도 좋습니다.
정답 : 11명
stack, queue를 이용한 풀이
#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n, k, num;
queue<int> moves;
stack<int> stk;
cin >> n >> k;
vector<queue<int>> board(n + 1);
for (int i = 0; i < k; i++)
{
cin >> num;
moves.push(num);
}
for (int i = 0; i < n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> num;
if (num) board[j].push(num);
}
}
int top, total = 0;
while (!moves.empty()) {
num = moves.front();
moves.pop();
if (!board[num].empty()) {
if (stk.empty()) top = 0;
else top = stk.top();
if (top == board[num].front() && !stk.empty()) {
stk.pop();
total += 2;
}
else {
stk.push(board[num].front());
}
board[num].pop();
}
}
cout << total;
return 0;
}
정답 : 10명
greedy를 이용한 풀이
#include <iostream>
#include <algorithm>
using namespace std;
struct Times
{
int start;
int end;
};
bool schedule(Times x, Times y) {
if (x.end != y.end)
return x.end < y.end;
else
return x.start < y.start;
}
int main()
{
int n;
cin >> n;
Times* times = new Times[n];
for (int i = 0; i < n; i++) {
cin >> times[i].start >> times[i].end;
}
sort(times, times + n, schedule);
int count = 0;
int end = -1;
for (int i = 0; i < n; i++) {
if (times[i].start >= end) {
count++;
end = times[i].end;
}
}
cout << count << endl;
return 0;
}
정답 : 5명
bfs를 이용한 풀이
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
#define pii pair<int, int>
int n, board[102][102], temp, robotBoard[102][102][2], dx[]={1,-1,0,0}, dy[]={0,0,1,-1};
queue<pair<pii, pii>> bfsQueue;
int main()
{
scanf("%d",&n);
for(int row=1; row<=n; ++row)
for(int col=1; col<=n; ++col){
scanf("%d",&temp);
//board에서 0을 장애물로 이용하기 위해 입력받은 값에서 0->1, 1->0으로 바꿔서 저장함
//이후로 1이 빈칸, 0이 장애물이 됨
//이 방법을 쓰면 저장되지 않은 board의 모든 칸이 장애물로 인식되어 따로 벽 처리해주지 않아도 됨
board[row][col] = !temp;
}
//robotBoard는 모두 0으로 초기화되어 있기 때문에 초기값과 방문값에 차이를 두기 위해 첫 좌표를 1로 설정함
//앞으로 0이면 방문하지 않은 좌표, 0이 아니면 방문했던 좌표가 됨
robotBoard[1][1][0] = 1;
bfsQueue.push(make_pair(make_pair(1,1),make_pair(1,2)));
//로봇의 왼쪽/위쪽 팔이 있는 좌표가 값을 저장할 좌표가 됨
//따라서 bfsQueue에 새로운 좌표를 넣을 때는 항상 first가 왼쪽/위쪽 팔의 좌표가 되도록 넣어야 함
while(!bfsQueue.empty()){
//mode는 0일 때 가로, 1일 때 세로를 뜻함. lu = left/up, rd = right/down, n = next를 뜻함
pii luPos = bfsQueue.front().first, rdPos = bfsQueue.front().second;
int lux = luPos.first, luy = luPos.second, rdx = rdPos.first, rdy = rdPos.second,
mode = luy == rdy, val = robotBoard[lux][luy][mode]+1;
bfsQueue.pop();
//cnt 0:아래쪽이동, 1:위쪽이동, 2:오른쪽이동, 3:왼쪽이동
for(int cnt=0; cnt<4; ++cnt){
int lunx = lux + dx[cnt], luny = luy + dy[cnt],
rdnx = rdx + dx[cnt], rdny = rdy + dy[cnt];
pii lunPos = make_pair(lunx,luny), rdnPos = make_pair(rdnx,rdny);
//로봇이 이동할 좌표가 모두 빈칸(=1)이라면
if(board[lunx][luny] && board[rdnx][rdny]){
//상하좌우용 코드
//다음 좌표를 방문하지 않았다면 방문값을 저장하고 bfsQueue에 넣음
if(!robotBoard[lunx][luny][mode]){
robotBoard[lunx][luny][mode] = val;
bfsQueue.push(make_pair(lunPos,rdnPos));
}
//회전용 코드
//로봇이 가로모드일 때 상/하로 이동할 수 있으면 좌상,우상/좌하,우하로 회전할 수 있음
//로봇이 세로모드일 때 좌/우로 이동할 수 있으면 좌상,좌하/우상,우하로 회전할 수 있음
//cnt<=1 : 상하이동, cnt>1 : 좌우이동, !mode : 세로모드, mode : 가로모드
if(cnt/2 == mode){ // == (cnt>1 && mode) || (cnt<=1 && !mode)
if(cnt%2){ //(cnt, mode) : (1,0), (3,1)
//로봇이 위쪽/왼쪽으로 이동했을 때는 원래 좌표보다 이동한 좌표가 더 작기 때문에 이동한 좌표를 기준으로 방문 여부를 확인함
if(!robotBoard[lunx][luny][!mode]){
robotBoard[lunx][luny][!mode] = val;
bfsQueue.push(make_pair(lunPos, luPos));
}
if(!robotBoard[rdnx][rdny][!mode]){
robotBoard[rdnx][rdny][!mode] = val;
bfsQueue.push(make_pair(rdnPos, rdPos));
}
}
else{ //(cnt,mode) : (0,0), (2,1)
//로봇이 아래쪽/오른쪽으로 이동했을 때는 원래 좌표가 이동한 좌표보다 더 작기 때문에 원래 좌표를 기준으로 방문 여부를 확인함
if(!robotBoard[lux][luy][!mode]){
robotBoard[lux][luy][!mode] = val;
bfsQueue.push(make_pair(luPos, lunPos));
}
if(!robotBoard[rdx][rdy][!mode]){
robotBoard[rdx][rdy][!mode] = val;
bfsQueue.push(make_pair(rdPos, rdnPos));
}
}
//if-else 없이 min,max 처리하면 코드 수가 줄어들지만, 보기 힘들까봐 min,max처리는 하지 않음
}
}
}
}
//(n,n)에 로봇이 걸치는 가로 좌표(n,n-1), 세로 좌표(n-1,n) 중 더 작은 값을 출력함
//0이면 10억을 반환해서 선택되지 않도록 하고 로봇의 시작점을 1로 잡았으니 1을 빼줌
printf("%d",min(robotBoard[n][n-1][0]?robotBoard[n][n-1][0]:1<<30,robotBoard[n-1][n][1]?robotBoard[n-1][n][1]:1<<30)-1);
return 0;
}
정답 : 6명
N, L = map(int, input().split())
board = [list(map(int, input().split())) for i in range(N)]
count = N*2
for way in board + [[board[j][i] for j in range(N)] for i in range(N)]:
height = way[0]
for i, h in enumerate(way):
if 2 <= abs(height-h):
count -= 1
break
elif 1 <= abs(height - h):
if h < height and i+L <= N and set(way[i:i+L]) == {h}:
height -= 1
way[i:i+L] = [h+0.5]*L
elif h > height and i-L >= 0 and set(way[i-L:i]) == {height}:
height += 1
way[i-L:i] = [h-0.5]*L
else:
count -= 1
break
print(count)
정답 : 3명
union-find를 이용한 풀이
//solving with union-find, backtracking : 80ms
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
#define max(a,b) (a>b?a:b)
int n, v, left, right, leftGroup[100002], rightGroup[100002], disFromRoot[100002];
long long res;
stack<int> vStack;
stack<pair<int,pair<int,int>>> rangeStack;
int findLeft(int num){
if(leftGroup[num] == num) return num;
else return leftGroup[num] = findLeft(leftGroup[num]);
}
int findRight(int num){
if(rightGroup[num] == num) return num;
else return rightGroup[num] = findRight(rightGroup[num]);
}
//알고리즘 배경
//이진트리의 빠른 삽입은 삽입하고자 하는 값과 가장 가까이에 있는 값 중 비어있는 가지에 넣는 것이다.
//예시로 이진트리 안에 1 6 4 2 순으로 넣었다면 5를 넣을 때는 4와 6 중에 비어있는 가지인 4오른쪽에 넣고(6왼쪽에는 4가 들어가 있다)
//5가 들어간 후 3을 넣는다면 2와 4 중에 비어있는 가지인 2의 오른쪽에 넣는 것이다.(4왼쪽에는 2가 들어가 있다)
//여기서 문제는 '삽입하고자 하는 값과 가장 가까운 두 수를 어떻게 얻을 것인가' 이다.
//만약 O(1)만에 값을 얻고자 가장 가까운 두 수를 저장하는 배열을 만들었다고 해보자.
//초기에는 배열1은 모드 0으로 초기화 되어 있고, 배열2는 n+1로 초기화 되어 있을 것이다.
//하지만 값을 삽입한 뒤, 배열1은 [값,n]구간을 값으로 업데이트하고, 배열2는 [1,값]구간을 값으로 업데이트하면 시간적 손실이 굉장히 많이 나게 된다.
//여기서 두 배열은 모든 값을 삽입한 후 (배열[값] == 값) 이라는 특성을 이용해 백트래킹을 진행한다.
int main()
{
scanf("%d",&n);
for(int cnt=0;cnt<n;++cnt){
scanf("%d",&v);
vStack.push(v);
}
//union-find 초기 세팅, 여기서 자기자신을 가리킨다는 건 이진트리에 삽입되어 있음을 의미함
for(int cnt=0;cnt<=100001;++cnt)
leftGroup[cnt] = rightGroup[cnt] = cnt;
while(!vStack.empty()){
v = vStack.top(); vStack.pop();
//자신과 가장 가까이에 있는 왼쪽값과 오른쪽 값을 구함
left = findLeft(v-1), right = findRight(v+1);
//자신은 이제 트리에 없는 값이 될 것이므로 자신을 가리키지 않도록 왼쪽과 오른쪽 값을 저장함
leftGroup[v] = left, rightGroup[v] = right;
//재귀함수 스택 오버플로우 방지용
//[v,right-1], [left+1,v] 구간에 있는 모든 값은 모두 이진트리에 없기 때문에 이를 이용해 배열을 업데이트 함
findLeft(right-1), findRight(left+1);
//삽입할 값과 가장 가까운 왼쪽값, 오른쪽값을 스택에 저장함
rangeStack.push(make_pair(v,make_pair(left,right)));
}
while(!rangeStack.empty()){
v = rangeStack.top().first, left = rangeStack.top().second.first, right = rangeStack.top().second.second;
rangeStack.pop();
//구간 중 루트와 거리가 더 먼 노드를 채택해 v노드에 기록하고 result에 높이를 반영함
res+=(disFromRoot[v] = max(disFromRoot[left], disFromRoot[right])+1)-1;
printf("%lld\n",res);
}
return 0;
}
map과 binary search를 이용한 풀이
/*
이진 탐색 트리
N의 크기는 10만
C의 값은 곧 랭크 누적
매번 insert 함수를 수행한다면
시간복잡도는 O(N)이므로 수행 시간을 보장할 수 없다.
또한 최악의 경우 편향 이진 트리가 될 수 있어 O(N^2)
이진탐색트리 삽입 원리를 이해하자
*/
#include <iostream>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;
map<int, int> m;
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
long long C = 0;
int depth;
/*
최대 최소 값 처리 테크닉
*/
m.insert({0,-1});
m.insert({100005, -1});
for(int i = 0; i < n; i++){
int num;
cin >> num;
auto up_iter = m.upper_bound(num);
auto low_iter = up_iter;
--low_iter;//후위 연산자를 사용하면 이전 값을 반환하기 때문에 임시 객체가 생겨 성능이 낮아진다고 함.
depth = max(up_iter->second, low_iter->second) + 1;
m.insert({num, depth});
C += depth;
cout << C << '\n';
}
return 0;
}
Red-Black Tree를 이용한 풀이
중간에 제출한 답안이지만 성공 이력이 있고 의미가 있는 답변이라 생각해 추가합니다. 본 테스트 환경에서는 성공하지만 원본 문제(백준) 에서는 언어적 한계로 timeout됩니다.
import sys
input = sys.stdin.readline
# 참고글 : https://www.crocus.co.kr/641
# 참고글 : https://lsh424.tistory.com/73
# 참고글 : https://zeddios.tistory.com/237
class Node:
def __init__(self, data):
self.data = data
self.left = self.right = self.parent = None
self.color = 'R'
class RedBlackTree:
def __init__(self):
self.root = None
def find_gp_node(self,node):
try:
return node.parent.parent
except:
return None
def find_uncle_node(self,node):
grandparent_node = self.find_gp_node(node)
try:
if node.parent == grandparent_node.left:
return grandparent_node.right
else:
return grandparent_node.left
except:
return None
def rotate_left(self,node):
c = node.right
p = node.parent
# node와 c 위치 변경
try:
c.left.parent = node
except:
pass
node.right = c.left
node.parent = c
c.left = node
c.parent = p
# 만약 변경해 올라간 위치가 root라면
if c.parent == None:
self.root = c
# 아니라면 node의 원래 위치에 c 등록
else:
if p.left == node:
p.left = c
else:
p.right = c
def rotate_right(self,node):
c = node.left
p = node.parent
try:
c.right.parent = node
except:
pass
node.left = c.right
node.parent = c
c.right = node
c.parent = p
if c.parent == None:
self.root = c
else:
if (p.right == node):
p.right = c
else:
p.left = c
# case1. 루트 노드는 항상 블랙
# case2. 부모 노드가 블랙이면 회전, 색변환등 수행 필요 x, 하지만 빨강색이라면 case3 수행
def insert_case1(self,node):
try:
if node.parent.color == 'R':
self.insert_case3(node)
except:
node.color = 'B'
# case3. 부모노드, 삼촌노드 모두 빨강이라면 색변환 수행, 아닐경우 case4로 이동
def insert_case3(self,node):
uncle = self.find_uncle_node(node)
if (uncle != None and uncle.color == 'R'):
node.parent.color = 'B'
uncle.color = 'B'
grandparent = self.find_gp_node(node)
grandparent.color = 'R'
self.insert_case1(grandparent)
else:
self.insert_case4(node)
# case4,5 회전 수행
def insert_case4(self,node):
grandparent = self.find_gp_node(node)
if(node == node.parent.right and node.parent == grandparent.left):
self.rotate_left(node.parent)
node = node.left
elif (node == node.parent.left and node.parent == grandparent.right):
self.rotate_right(node.parent)
node = node.right
node.parent.color = 'B'
grandparent.color = 'R'
if (node == node.parent.left):
self.rotate_right(grandparent)
else:
self.rotate_left(grandparent)
# 삽입
def insert(self, data):
node, bigger_min, smaller_max = self.insert_value(data)
self.insert_case1(node)
return bigger_min, smaller_max
# 재귀에서 while로 바꾸고 항상 한개의 데이터만 입력받게 바꿈.
def insert_value(self, data):
if self.root == None:
self.root = Node(data)
return self.root, None, None
node = self.root
parent_node = smaller_max = bigger_min= None
# min max 안달아도 될 것 같긴함.
while node != None:
parent_node = node
if data < node.data:
bigger_min = node.data
node = node.left
else:
smaller_max = node.data
node = node.right
node = Node(data)
node.parent = parent_node
if data < parent_node.data:
parent_node.left = node
else:
parent_node.right = node
return node, bigger_min, smaller_max
class BinaryNode:
def __init__(self, depth):
self.depth = depth
self.right = self.left = None
'''
def check(node):
if not node.left == None : check(node.left)
if node.parent != None:
print('key: ', node.data, 'parents: ', node.parent.data, 'color: ', node.color, end = '\n')
else:
print('key: ', node.data, 'parents: ', node.parent, 'color: ', node.color, end = '\n')
if not node.right == None : check(node.right)
'''
def solve():
N = int(input())
values = list(map(int, input().split()))
rb_tree = RedBlackTree()
tree = [0] * (N + 1)
result_str = ""
result = 0
for value in values:
bigger_min, smaller_max = rb_tree.insert(value)
depth = 1
try:
if tree[bigger_min].left == None:
tree[bigger_min].left = value
depth = tree[bigger_min].depth + 1
except:
pass
try:
if tree[smaller_max].right == None:
tree[smaller_max].right = value
depth = tree[smaller_max].depth + 1
except:
pass
tree[value] = BinaryNode(depth)
result += depth - 1
result_str += str(result) + '\n'
print(result_str)
solve()
모범 답안 작성 후 해설 작성시 모범 답안 채택 갯수 시상
에 우대합니다(동점자 발생시). 모범 답안 선정되신 분들은 다른 학우분들이 코드를 보고 공부하실 수 있도록 해설 남겨주시면 감사드리겠습니다.
코드에 주석으로 달아주신 분들은 해설을 작성해주신것으로 간주하겠습니다. 물론 추가 해설을 작성해주시면 너무 감사드립니다.
해설은 본 이슈에 계속 달아주세요!
모범 답안 및 해설에 대한 질문이 있으신 분들도 여기에 같이 남겨주시면 좋을 것 같습니다. 슬랙 #dcomding 채널을 이용해주셔도 좋습니다.
오류 제보 및 피해자 기록
정답 : 11명
chars = input()
chars += chars[0] # dummy
answer = 0
for i in range(1, len(chars) - 1):
if chars[i] != chars[0] and chars[i] != chars[i + 1]:
answer += 1
print(answer)
정답 : 8명
dp를 이용한 풀이
#dp[i] : i번째 위치에서 넣을 수 있는 상자의 최대 갯수
n = int(input())
boxes = list(map(int, input().split()))
dp = [1 for _ in range(n)]
for i in range(1, n):
for j in range(i):
if boxes[j] < boxes[i]:
dp[i] = max(dp[i], dp[j]+1) # +1 : i번째 상자 포함
print(max(dp))
정답 : 6명
Priority Queue를 이용한 풀이
import heapq
import sys
input = sys.stdin.readline
def solve():
N = int(input())
values = [0] * N
for i in range(N):
values[i] = tuple(map(int,input().split()))
values.sort()
# heapq로 현재 사용 중인 자리의 끝나는 시간을 담고 있음.
end_que = []
# heapq로 현재 사용 가능한 자리의 idx를 담고 있음.
idx_que = []
# 각 자리별 사용 인원 수
cache = [0] * N
nxt_idx = 0
for start,end in values:
# 현재 사용 중인 인원이 있다면
if len(end_que):
# 그 중 가장 빨리 끝나는 사람을 찾는다.
fastest_end, fastest_idx = end_que[0]
# 만약 fastest_end가 start 보다 작다면 (즉 그 자리를 쓸 수 있다면)
if fastest_end <= start:
try:
# fastest_end가 start보다 커지거나 end_que가 빌때까지
# 계속 빼내서 idx_que에 넣음
while fastest_end <= start:
f_end, f_idx = heapq.heappop(end_que)
heapq.heappush(idx_que, f_idx)
fastest_end, fastest_idx = end_que[0]
except:
pass
try:
# idx_que에 value가 있다면 가장 빠른 자리를 찾는다.
idx = heapq.heappop(idx_que)
cache[idx] += 1
heapq.heappush(end_que, (end, idx))
continue
except:
pass
# 사용중인 인원이 없거나, 빈자리가 없고 가장 빨리 끝나는 사람이 내 시작시간보다 느리면
# 새로운 자리를 추가한다.
cache[nxt_idx] += 1
heapq.heappush(end_que, (end, nxt_idx))
nxt_idx += 1
print(nxt_idx)
print(*cache[:nxt_idx])
solve()
세그먼트 트리를 이용한 풀이
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
#define pii pair<int,int>
int n, st, ed, segTree[1<<21], ptr=1<<20;
vector<pii> timetable;
vector<int> computers, endTimes;
map<int,priority_queue<int>> timeComputer;
void update(int num, int val){
segTree[num+=ptr] = val;
while(num>>=1)
segTree[num] = min(segTree[num*2], segTree[num*2+1]);
}
int getMin(int st, int ed){
st+=ptr, ed+=ptr;
int res = 1000001;
while(st<=ed){
if(st%2==1) res = min(res, segTree[st]), ++st;
if(ed%2==0) res = min(res, segTree[ed]), --ed;
st>>=1, ed>>=1;
}
return res;
}
int main()
{
scanf("%d",&n);
for(int cnt=0; cnt<n; ++cnt){
scanf("%d%d",&st,&ed);
timetable.push_back(make_pair(st,ed));
}
sort(timetable.begin(), timetable.end());
fill(segTree, segTree+ptr*2, 1000001);
for(auto iter = timetable.begin(); iter != timetable.end(); ++iter){
int minPos = getMin(0, iter->first);
if(!timeComputer.count(iter->second))
timeComputer.insert(make_pair(iter->second, priority_queue<int>()));
if(minPos == 1000001){
timeComputer[iter->second].push(-computers.size());
if(timeComputer[iter->second].top() == -computers.size())
update(iter->second, computers.size());
computers.push_back(1);
endTimes.push_back(iter->second);
}
else{
++computers[minPos];
timeComputer[endTimes[minPos]].pop();
if(!timeComputer[endTimes[minPos]].empty())
update(endTimes[minPos], -timeComputer[endTimes[minPos]].top());
else
update(endTimes[minPos], 1000001);
timeComputer[endTimes[minPos]=iter->second].push(-minPos);
if(timeComputer[iter->second].top() == -minPos)
update(iter->second, minPos);
}
}
printf("%d\n", computers.size());
for(auto iter = computers.begin(); iter != computers.end(); ++iter)
printf("%d ", *iter);
return 0;
}
정답 : 3명
Linked List를 이용한 풀이
import sys
input = sys.stdin.readline
class Node:
def __init__(self,idx):
self.idx = idx
self.bef = None
self.nxt = None
def solution():
n,f,k = map(int, input().split())
# linked list 초기화
values = [Node(i) for i in range(n)]
for i in range(n):
try:
values[i].nxt = values[i + 1]
except:
pass
try:
values[i+1].bef = values[i]
except:
pass
deleted = [] # stk
cur = values[f]
for i in range(k):
comm = list(input().split())
if comm[0] == "U":
for _ in range(int(comm[1])):
cur = cur.bef
elif comm[0] == "D":
for _ in range(int(comm[1])):
cur = cur.nxt
elif comm[0] == "C":
deleted.append(cur.idx)
cur.idx = -1
try:
cur.bef.nxt = cur.nxt
except:
pass
try:
cur.nxt.bef = cur.bef
cur = cur.nxt
except:
# 마지막이라서 nxt가 없다면
cur = cur.bef
else:
restore = deleted.pop()
target = values[restore]
target.idx = restore
nxt = target.nxt
try:
while nxt.idx == -1:
nxt = target.nxt
if nxt.bef != None:
nxt.bef.nxt = target
target.bef = nxt.bef
nxt.bef = target
target.nxt = nxt
except:
bef = target.bef
while bef.idx == -1:
bef = target.bef
if bef.nxt != None:
bef.nxt.bef = target
target.nxt = bef.nxt
bef.nxt = target
target.bef = bef
pass
deleted.sort()
result = ""
for i in deleted:
result += str(i) + "\n"
print(result)
solution()
펜윅트리를 이용한 풀이
#include <cstdio>
#include <algorithm>
using namespace std;
#define pii pair<int,int>
int n, f, k, num, delName[1000001], delPtr, fwTree[1000010];
char command;
void update(int num, int val){
while(num<=n)
fwTree[num] += val, num += (num & -num);
}
int getSum(int ed){
int res = 0;
while(ed)
res += fwTree[ed], ed -= (ed & -ed);
return res;
}
int bs(int val){
int l=1, r=n, m;
while(l<=r){
m=(l+r)/2;
if(getSum(m)<=val) l=m+1;
else r=m-1;
}
return l;
}
int main()
{
scanf("%d%d%d",&n,&f,&k); ++f; getchar();
for(int cnt=1; cnt<=n; ++cnt)
update(cnt, 1);
for(int cnt=0; cnt<k; ++cnt){
scanf("%c",&command);
switch(command){
case 'U':
scanf("%d",&num); getchar();
f = bs(getSum(f)-num-1);
break;
case 'D':
scanf("%d",&num); getchar();
f = bs(getSum(f)+num-1);
break;
case 'C':
getchar();
delName[delPtr] = f;
if(f==bs(n-delPtr-1)) f = bs(getSum(f)-2);
else f = bs(getSum(f));
update(delName[delPtr++], -1);
break;
case 'Z':
getchar();
update(delName[--delPtr],1);
break;
}
}
sort(delName, delName+delPtr);
for(int cnt=0; cnt<delPtr; ++cnt)
printf("%d\n",delName[cnt]-1);
return 0;
}
정답 : 4명
Trie를 이용한 풀이
import sys
input = sys.stdin.readline
def solution():
# 알파벳 하나 하나를 가지는 dictonary 중첩으로 푼다.
# 만약 dict[char]의 len이 1이라면 자동완성이 되는걸로 쳐서 count를 하지 않는다.
n = int(input())
words = [0] * n
# root에 tmp를 추가해 시작 알파벳이 다 같은 경우여도 count가 1은 나오게 해줘서
# 첫글자는 자동완성이 안되는 것처럼 했다.
root = {}
root[""] = 0
for i in range(n):
# 단어를 입력받고
words[i] = input().rstrip()
cur = root
# 각 단어의 글자마다 dict 안을 들어간다.
for char in words[i]:
try:
cur = cur[char]
except:
cur[char] = {}
cur = cur[char]
# 해당 단어에서 끝나는 경우와 그 이상으로 이어지는 경우 거르기 위해 tmp 추가
cur[""] = 0
result = ""
# 각 단어로 쭉 파고 들어가면서 count 한다.
for i in range(n):
count = 0
cur = root
for char in words[i]:
if len(cur) != 1:
count += 1
cur = cur[char]
result += str(count) + "\n"
print(result)
solution()
모범 답안 작성 후 해설 작성시 모범 답안 채택 갯수 시상
에 우대합니다(동점자 발생시). 모범 답안 선정되신 분들은 다른 학우분들이 코드를 보고 공부하실 수 있도록 해설 남겨주시면 감사드리겠습니다.
코드에 주석으로 달아주신 분들은 해설을 작성해주신것으로 간주하겠습니다. 물론 추가 해설을 작성해주시면 너무 감사드립니다.
해설은 본 이슈에 계속 달아주세요!
모범 답안 및 해설에 대한 질문이 있으신 분들도 여기에 같이 남겨주시면 좋을 것 같습니다. 슬랙 #dcomding 채널을 이용해주셔도 좋습니다.
6-7위
와 8-9위
는 동점자 처리 규칙에 의해 고난이도 문제 푼 갯수
순으로 결정되었음.
정답 : 14명
set을 이용한 풀이
n, k = map(int, input().split())
l = len(list(set(map(int, input().split()))))
print(l if k > l else k)
정답 : 14명
DP를 이용한 풀이
#dp(n) = max(dp(n), dp(i)+p(i))
#dp(n) : n일까지의 수익
#n일 이전에 받을 수 있는 모든 경우중 가장 큰값으로 갱신
n = int(input())
table = []
dp = []
answer = 0
for i in range(n):
t, p = map(int, input().split())
table.append((t, p))
dp.append(p)
#날짜를 초과하지 않는 선에서 단순히 수익만 계산
for i in range(1, n):
for j in range(i):
if j + table[j][0] <= i:
dp[i] = max(dp[i], dp[j]+table[i][1])
#dp(i) = max(i일까지의 수익, j일까지의 수익 + i일의 수익)
#여기서 실제 그 외주를 맡았을 때 할 수 있는지 검사
for i in range(n):
if i+table[i][0] <= n:
if answer < dp[i]:
answer = dp[i]
print(answer)
DFS를 이용한 풀이
n ≤ 15 이므로 dfs로 풀어도 시간 안에 해결 가능
#include <iostream>
#include <vector>
using namespace std;
void DFS(vector<vector<int>>& table, int index, int total, int& max) {
int size = table.size();
for (int i = index; i < size; i++)
{
if (i + table[i][0] <= size)
{
total += table[i][1];
DFS(table, i + table[i][0], total, max);
total -= table[i][1];
}
}
if (total > max) max = total;
}
int main() {
int n, t, p, total = 0, max = 0;
vector<vector<int>> table;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> t >> p;
table.push_back({ t, p });
}
DFS(table, 0, 0, max);
cout << max;
return 0;
}
정답 : 11명
n, t, m, k = map(int, input().split())
passengers = sorted([(lambda x: int(x[0])*60 + int(x[1]))(input().split()) for i in range(k)], reverse=True)
for time in range(9*60 + 0, 23*60 + 59, t)[:n]:
bus = [passengers.pop() for i in range(m) if passengers and passengers[-1] <= time]
if len(bus) == m:
time = bus[-1] - 1
print(time//60, time%60)
정답 : 4명
DFS와 MST를 이용한 풀이
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int campus[11][11], n, m;
vector<pair<int, pair<int, int>>> bridges;
//2차원 배열의 유효한 위치인 지 확인하는 함수
bool canGotoPos(int x, int y){
return 0<=x && x<n && 0<=y && y<m;
}
//dfs 건물, 다리 탐색용
int dx[]={1,-1,0,0}, dy[]={0,0,1,-1}, bCnt;
void dfs(int x, int y, int mode, int val){
//건물 탐색용
if(mode == -1){
campus[x][y] = val;
//4방향으로 뻗어가면서 더 이어진 부분이 있는 지 확인함
for(int cnt=0;cnt<4;++cnt){
int nx = x+dx[cnt], ny = y+dy[cnt];
if(canGotoPos(nx, ny) && campus[nx][ny] == -1)
dfs(nx, ny, mode, val);
}
}
//다리 탐색용
else{
int nx = x+dx[mode], ny = y+dy[mode];
if(canGotoPos(nx, ny)){
//다음 지점이 빈 공간이면 한칸 더감
if(campus[nx][ny] == 0)
dfs(nx, ny, mode, val+1);
//다음 지점이 자기 건물이 아니면서 거리가 1보다 크면 벡터에 저장. min,max는 나중에 중복된 다리를 없애기 위함임
else if(campus[nx][ny] != bCnt && val>1)
bridges.push_back(make_pair(val, make_pair(min(bCnt, campus[nx][ny]), max(bCnt, campus[nx][ny]))));
}
}
}
//union-find 함수
int group[7];
int findGroup(int bNum){
if(bNum == group[bNum]) return bNum;
return group[bNum] = findGroup(group[bNum]);
}
int main() {
scanf("%d%d",&n,&m);
for(int nCnt = 0; nCnt<n; ++nCnt)
for(int mCnt = 0; mCnt<m; ++mCnt){
scanf("%d",&campus[nCnt][mCnt]);
//건물의 번호가 1번부터 시작하므로 건물의 존재여부와 건물번호에 차이를 두기 위해 건물의 존재여부는 -1로 저장함
campus[nCnt][mCnt] = -campus[nCnt][mCnt];
}
//dfs를 통해 건물 특정짓기
int totalBuilding = 0;
for(int nCnt = 0; nCnt<n; ++nCnt)
for(int mCnt = 0; mCnt<m; ++mCnt)
//방문한 지점에 번호가 매겨지지 않은 건물이 있으면 건물에 번호를 붙여줌
if(campus[nCnt][mCnt] == -1)
dfs(nCnt, mCnt, -1, ++totalBuilding);
//dfs를 통해 각 건물을 연결하는 다리 만들기. bCnt는 dfs()에서도 사용됨
for(bCnt = 1; bCnt<=totalBuilding; ++bCnt)
for(int nCnt = 0; nCnt<n; ++nCnt)
for(int mCnt = 0; mCnt<m; ++mCnt)
//방문한 지점이 건물이면 한 방향으로 다리를 놓아봄
if(campus[nCnt][mCnt] == bCnt)
for(int cnt=0; cnt<4; ++cnt)
dfs(nCnt, mCnt, cnt, 0);
//unoin-find 초기 세팅
for(int cnt=1; cnt<=6; ++cnt)
group[cnt] = cnt;
//중복된 다리 제거
sort(bridges.begin(), bridges.end());
bridges.erase(unique(bridges.begin(), bridges.end()),bridges.end());
//최소 스패닝 트리를 이용한 간선 채택
int matchCnt=1, result=0;
for(int cnt=0; cnt<bridges.size(); ++cnt){
int val = bridges[cnt].first, x = bridges[cnt].second.first, y = bridges[cnt].second.second;
//채택된 두 건물이 서로 다른 그룹이면 다리를 선택함
if(findGroup(x) != findGroup(y))
group[findGroup(y)] = findGroup(x), ++matchCnt, result+=val;
//모든 건물이 한 그룹으로 묶였으면 다리 선택을 그만둠.
if(matchCnt == totalBuilding) break;
}
//모든 건물이 하나로 묶였으면 result, 아니면 불가능하다는 뜻이므로 -1을 출력
printf("%d",matchCnt==totalBuilding?result:-1);
return 0;
}
정답 : 3명
stack을 이용한 풀이
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
#define pii pair<int, int>
int n, h, result;
//histograms에는 항상 오름차순 높이만 존재하게끔 만듦 (뽑을 때는 내림차순으로 나옴)
stack<pii> histograms;
int main() {
scanf("%d",&n);
for(int cnt=0;cnt<n;++cnt){
scanf("%d",&h);
int possiblePtr = cnt;
while(!histograms.empty() && h<=histograms.top().first){
pii histogram = histograms.top(); histograms.pop();
//현재 높이에서 가능한 넓이와 result를 비교함
result = max(result, h*(cnt-histogram.second+1));
//스택에 있던 first는 현재 높이 h에서는 불가능하므로 h이전 위치까지의 넓이와 result를 비교함
//이게 가능한 이유는 histograms가 오름차순으로 들어가 있기 때문에 넓이가 보장됨.
result = max(result, histogram.first*(cnt-histogram.second));
//h보다 크거나 같은 높이값이기 때문에 second(=first 높이의 시작점)부터 최소 h만큼의 높이를 보장함
possiblePtr = histogram.second;
}
histograms.push(make_pair(h,possiblePtr));
}
//마지막으로 스택에서 빠지지 않은 (높이,시작점)들을 빼면서 최대값을 갱신함.
while(!histograms.empty()){
pii histogram = histograms.top(); histograms.pop();
result = max(result, histogram.first*(n-histogram.second));
}
printf("%d",result);
return 0;
}
분할 정복을 이용한 풀이
/*
모든 경우의 수를 탐색?
N^2이므로 10000000000 백억이므로 해결 불가
분할 정복 활용을 활용하자!
사각형이 왼쪽, 오른쪽, 걸쳐있을 케이스 고려
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> heights;
//left ~ right까지 찾을 수 있는 사각형 중 가장 큰 사각형 반환
int search(int left, int right){
if(left == right){//base
return heights[left];
}
int mid = (left + right) / 2;
//왼쪽, 오른쪽
int ret = max(search(left, mid), search(mid+1, right));
//걸쳐있을 케이스
int height = min(heights[mid], heights[mid+1]);
ret = max(ret, height * 2);
int l_idx = mid;
int r_idx = mid + 1;
while(left < l_idx || r_idx < right){
if(r_idx < right && (l_idx == left || heights[l_idx - 1] < heights[r_idx + 1])){
r_idx++;
height = min(height, heights[r_idx]);
}else{
l_idx--;
height = min(height, heights[l_idx]);
}
ret = max(ret, height * (r_idx - l_idx + 1));
}
return ret;
}
int main(){
cin >> N;
heights.resize(N);
for(int i = 0; i < N; i++){
cin >> heights[i];
}
cout << search(0 , N-1);
return 0;
}
모범 답안 작성 후 해설 작성시 모범 답안 채택 갯수 시상
에 우대합니다(동점자 발생시). 모범 답안 선정되신 분들은 다른 학우분들이 코드를 보고 공부하실 수 있도록 해설 남겨주시면 감사드리겠습니다.
코드에 주석으로 달아주신 분들은 해설을 작성해주신것으로 간주하겠습니다. 물론 추가 해설을 작성해주시면 너무 감사드립니다.
해설은 본 이슈에 계속 달아주세요!
모범 답안 및 해설에 대한 질문이 있으신 분들도 여기에 같이 남겨주시면 좋을 것 같습니다. 슬랙 #dcomding 채널을 이용해주셔도 좋습니다.
정답 : 9명
투 포인터를 이용한 풀이
def check(s,left,right):
while left<right:
if s[left]==s[right]:
left+=1
right-=1
else:
return False
return True
def twopointer(s,left,right):
while left<right:
if s[left]==s[right]:
left+=1
right-=1
else:
if check(s,left+1,right) or check(s,left,right-1): #그 전후 원소들은 볼필요가 없다 이미 같으니까!
return 1
return 2
return 0
s = input()
print(twopointer(s,0, len(s)-1))
정답 : 4명
dfs를 이용한 풀이
#include <iostream>
using namespace std;
int paper[10][10];
int colorpaper[5] = { 0,0,0,0,0 };
int answer = 26;
bool is_square(int x, int y, int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (paper[x + i][y + j] == 0)
return false;
}
}
return true;
}
void glue(int x, int y, int count) {
while (paper[x][y] == 0) {
y++;
if (y == 10) {
x++;
if (x == 10){
if (count < answer)
answer = count;
return;
}
y = 0;
}
}
if (answer <= count)
return;
for (int i = 5; i > 0; i--) {
if (x + i <= 10 && y + i <= 10 && colorpaper[i] < 5 && is_square(x, y, i) == true) {
for (int j = 0; j < i; j++) {
for (int k = 0; k < i; k++) {
paper[x + j][y + k] = 0;
}
}
colorpaper[i]++;
glue(x, y, count + 1);
for (int j = 0; j < i; j++) {
for (int k = 0; k < i; k++) {
paper[x + j][y + k] = 1;
}
}
colorpaper[i]--;
}
}
}
int main() {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++)
cin >> paper[i][j];
}
glue(0, 0, 0);
if (answer > 25)
answer = -1;
cout << answer << endl;
return 0;
}
정답 : 2명
pq + 비트마스킹을 이용한 풀이
def solution():
from heapq import heappop, heappush
import sys
input = sys.stdin.readline
MAX = sys.maxsize
n,m,k,start,end = map(int,input().split())
traps = list(map(int,input().split()))
trap_checker = [-1] * (n + 1)
for i in range(k):
trap_checker[traps[i]] = i
roads = {i:{} for i in range(1,n + 1) }
reversed_roads = {i:{} for i in range(1,n + 1) }
for i in range(m):
p,q,t = map(int,input().split())
try:
roads[p][q] = min(t, roads[p][q] )
reversed_roads[q][p] = min(t, reversed_roads[q][p] )
except:
roads[p][q] = t
reversed_roads[q][p] = t
# 함정방의 최대 개수가 10개이므로 비트마스크를 써야함.
# road를 각 함정방의 경우에 수의 따라 다 만들어 놓자. -> 시간 초과의 원인이 이거네
# 최대가 3000 * 1000 = 3백만
bit_max = pow(2,k)
bit_check = [pow(2, i) for i in range(k)]
visited = [[0] * (n + 1) for i in range(bit_max)]
findings = []
# cost, cur_pos, bit_idx
heappush(findings, (0, start, 0))
def visit(bit_idx, cur_cost,nxt_pos, cost):
# 다음 길이 트랩이라면
if trap_checker[nxt_pos] != -1:
new_bit_idx = bit_idx ^ bit_check[trap_checker[nxt_pos]]
if visited[new_bit_idx][nxt_pos]:
return
heappush(findings, (cur_cost + cost, nxt_pos, new_bit_idx))
else:
if visited[bit_idx][nxt_pos]:
return
heappush(findings, (cur_cost + cost, nxt_pos, bit_idx))
def is_reversed(bit_idx,pos):
if trap_checker[pos] != -1 and bit_idx & bit_check[trap_checker[pos]]:
return True
return False
while findings:
cur_cost, cur_pos, bit_idx = heappop(findings)
if visited[bit_idx][cur_pos]:
continue
# 종결 조건
if cur_pos == end:
return cur_cost
visited[bit_idx][cur_pos] = 1
# 이번이 거꾸로 되있다면.
if trap_checker[cur_pos] != -1 and bit_idx & bit_check[trap_checker[cur_pos]]:
# 역방향 간선들에 대해
for nxt_pos in reversed_roads[cur_pos].keys():
cost = reversed_roads[cur_pos][nxt_pos]
if is_reversed(bit_idx,nxt_pos):
continue
visit(bit_idx, cur_cost,nxt_pos, cost)
# 역방항에서 정방향 간선으로 갈 수 있는 경우는 얘네가 함정인 경우 뿐
for nxt_pos in traps:
try:
cost = roads[cur_pos][nxt_pos]
if bit_idx & bit_check[trap_checker[nxt_pos]]:
visit(bit_idx, cur_cost,nxt_pos, cost)
except:
continue
else: # 여기가 정방향이면
for nxt_pos in roads[cur_pos].keys():
cost = roads[cur_pos][nxt_pos]
if is_reversed(bit_idx,nxt_pos):
continue
visit(bit_idx, cur_cost,nxt_pos, cost)
for nxt_pos in traps:
try:
cost = reversed_roads[cur_pos][nxt_pos]
if bit_idx & bit_check[trap_checker[nxt_pos]]:
visit(bit_idx, cur_cost,nxt_pos, cost)
except:
continue
return -1
print(solution())
모범 답안 작성 후 해설 작성시 모범 답안 채택 갯수 시상
에 우대합니다(동점자 발생시). 모범 답안 선정되신 분들은 다른 학우분들이 코드를 보고 공부하실 수 있도록 해설 남겨주시면 감사드리겠습니다.
코드에 주석으로 달아주신 분들은 해설을 작성해주신것으로 간주하겠습니다. 물론 추가 해설을 작성해주시면 너무 감사드립니다.
해설은 본 이슈에 계속 달아주세요!
모범 답안 및 해설에 대한 질문이 있으신 분들도 여기에 같이 남겨주시면 좋을 것 같습니다. 슬랙 #dcomding 채널을 이용해주셔도 좋습니다.
이름 | 1점 답안 | 1점 해설 | 2점 답안 | 2점 해설 | 3점 답안 | 3점 해설 | 4점 답안 | 4점 해설 | 총점 |
---|---|---|---|---|---|---|---|---|---|
손현수 | 1 | 0 | 1 | 1 | 8 | 5 | 3 | 3 | 68 |
심규진 | 0 | 0 | 1 | 1 | 4 | 1 | 3 | 3 | 43 |
송용우 | 0 | 0 | 0 | 0 | 2 | 0 | 2 | 2 | 22 |
전현준 | 1 | 0 | 4 | 0 | 3 | 0 | 0 | 0 | 18 |
윤창목 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 14 |
황지원 | 2 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 11 |
구희연 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 10 |
최성원 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 0 | 8 |
박민재 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 8 |
손지언 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 7 |
나혜원 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 5 |
박진수 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 3 |
장예원 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 3 |
장재훈 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
의미 있는 주석을 작성한 경우 해설로 인정했습니다.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.