일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
- 다익스트라
- LazyPropagation
- DP
- 누적합
- 수학
- 크루스칼
- 백준
- 이분매칭
- dfs
- 정렬
- lca
- boj
- 그리디
- 펜윅트리
- 이분탐색
- MST
- 삼분탐색
- 구현
- 브루트포스
- DisjointSet
- 세그먼트트리
- 플로이드와샬
- 좌표압축
- BFS
- 위상정렬
- lis
- 에라토스테네스의 체
- 투포인터
- 비트마스크
- 이진탐색
- Today
- Total
목록전체 글 (127)
lastknight00
문제 링크 : [백준]The Other Way(14554) 14554번: The Other Way 첫째 줄에는 $N$, $M$, $S$, $E$가 하나의 공백으로 구분되어 들어온다. ($2 \le N \le 100000$, $N-1 \le M \le 300000$, $1 \le S, E \le N$, $S \neq E$) 그 후 $M$개의 줄에는 $A$, $B$, $C$가 하나의 공백으로 구분 되어 들어 www.acmicpc.net 문제 설명 N개의 노드와 M개의 양방향 간선이 주어질 때, 시작점에서 도착점까지 최단거리로 가는 경로의 갯수를 구하세요. 입력 N(노드의 갯수, 1 m>>s>>e; for(x=1;x>x>>y>>z; v[x].push_back({y,z}); v[y].push_back({x,z}..
문제 링크 : [백준]물대기(1368) 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 문제 설명 N개의 논에 직접 우물을 파거나, 이미 물을 대고 있는 논에서 물을 끌어옴 두 가지 작업을 통하여 모든 논에 물을 대고자 합니다. 두 가지에 대한 비용이 주어졌을 때, 모든 논에 물을 대는 최소 비용을 구하세요. 입력 N(논의 갯수, 1
문제 링크 : [백준]평균값 수열(5485) 5485번: 평균값 수열 다음과 같은 4가지 경우만이 존재한다 : {2,2,8,10} / {1,3,7,11} / {0,4,6,12} / {-1,5,5,13} www.acmicpc.net 문제 설명 A1, A2, A3...의 수열이 주어집니다. 이 수열은 차례로 (X1 + X2) / 2, (X2 + X3) / 2, (X3 + X4) /2 를 의미하는 수입니다. X1, X2...가 순서대로 비내림차순으로 이루어진다고 할 때, 가능한 수열의 경우의 수를 구하세요. 입력 N(원소의 갯수, 2
문제 링크 : [백준]무한이진트리(2078) 2078번: 무한이진트리 첫째 줄에 두 정수 A, B(1≤A, B≤2,000,000,000)가 주어진다. 잘못된 입력은 주어지지 않는다고 가정한다. www.acmicpc.net 문제 설명 루트가 (1, 1)의 값을 갖는 노드로 이루어지며, 왼쪽 자식은 (2, 1), 오른쪽 자식은 (1, 2)로 이루어집니다. 반복적으로 왼쪽 자식은 (부모의 왼쪽 값 + 부모의 오른쪽 값, 부모의 오른쪽 값), 오른쪽 자식은 (부모의 왼쪽 값, 부모의 왼쪽 값 + 부모의 오른쪽 값) 으로 구성됩니다. 이 때, 왼쪽 값과 오른쪽 값이 주어졌을 때, 해당 값이 나오는 노드에 도착하기 위하여 루트 노드에서 왼쪽, 오른쪽으로 몇번을 이동해야 하는지 구하세요. 입력 A B(왼쪽 값과 오른..
문제 링크 : [백준]기업투자(2662) 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 � www.acmicpc.net 문제 설명 기업별로 투자 금액 별 수익금이 주어집니다. N원을 투자하여 최대로 수익을 얻을 수 있는 금액과 어떤 기업에 얼마를 투자해야 하는지 구하세요. 입력 N(투재 금액, 1
문제 링크 : [백준]대한민국(3770) 3770번: 대한민국 입력의 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N, M, K가 주어진다. K는 고속도로의 수이다. 둘째 줄부터 K개의 줄에는 고속도로의 정보가 주어진다. 고� www.acmicpc.net 문제 설명 왼쪽 도시에서 오른쪽 도시로 연결하는 고속도로들 중 교차점의 갯수를 구하세요. 입력 T(테스트 케이스 수) N(왼쪽 도시 갯수, 1 k; for(i=0;i>d[i].F>>d[i].S,d[i].F*=-1,d[i].S*=-1; sort(d,d+k); for(a=i=0;i
문제 링크 : [백준]소가 길을 건너간 이유 11(14459) 14459번: 소가 길을 건너간 이유 11 우리는 존의 고민을 해결해 줄 방법을 찾았지만, 그걸 알려 주러 가다가 길을 잃었다. 존의 농장에 가긴 했지만, 2N개의 목초지는 없고 웬 N×N 격자가 있는 것이다. 알고 보니 우리는 동명이인의 � www.acmicpc.net 문제 설명 왼쪽 길에서 오른쪽 길로 횡단보도를 만들려고 합니다. 그러나 각 왼쪽 지점에서 오른쪽 지점으로 잇기 위해서는 각 지점에 있는 숫자의 차이가 4이하여야 횡단보도를 지을 수 있습니다. 또한 횡단보도가 서로 엇갈리지 않도록 지어야합니다. 이때 최대한 많이 만들 수 있는 횡단보도의 갯수를 구하세요. 입력 N(지점의 갯수, 1
문제 링크 : [백준]우체국(2285) 2285번: 우체국 첫째 줄에 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 X[1] A[1], X[2] A[2], …, X[N] A[N]이 주어진다. 범위는 |X[i]|≤1,000,000,000, 0≤A[i]≤1,000,000,000 이며 모든 입력은 정수이다. 모든 A[i]를 합친 값은 0 www.acmicpc.net 문제 설명 N개의 마을이 있고, 각 마을은 Xi에 위치하고, Ai명의 사람이 산다고 합니다. 이 때, 특정 위치에 우체국을 세웠을 때, 모든 사람과 우체국간의 거리가 최소가 되는 우체국의 위치를 구하세요. 입력 N(마을의 갯수, 1
문제 링크 : [백준]블록 쌓기(9998) 9998번: 블록 쌓기 윤형이와 동혁이가 블록 쌓기 놀이를 한다. 두 명 모두 너비 N의 블록 건물을 쌓았는데, 윤형이는 k번째 열에 Yk개의 블록을 쌓았고 동혁이는 k번째 열에 Dk개의 블록을 쌓았다. 윤형이와 동혁이는 www.acmicpc.net 문제 설명 N칸에 걸쳐 블록을 임의의 높이로 두 줄이 쌓여있습니다. 두 줄의 블록을 가운데를 가장 낮게 하는 V자 형태로 변경하고 싶습니다. 쌓여있는 블록을 빼거나, 추가할 수 있는데, 이 행동을 가장 적게 수행하여 V자로 만드는 횟수를 구하세요. 입력 N(칸의 갯수, 1
문제 링크 : [백준]빌보의 생일(4442) 4442번: 빌보의 생일 프로도와 샘은 다가오는 빌보의 111번째 생일 파티를 계획하려고 한다. 그들은 중간계의 모든 호빗을 생일 파티에 초대했고, 단 한 명의 예외도 없이 모두 참석하기로 했다. 호빗은 한 줄로 되어� www.acmicpc.net 문제 설명 프로도와 샘이 각각 생일 파티에 참가한 사람들을 순서대로 앉힐 좌석표를 작성하였습니다. 두 좌석표가 일치하지 않을 수 있어서 새로운 좌석표를 만드는데, 원래 있던 두 좌석표와 다른 쌍이 최소가 되게 하려고 합니다. 이 때, 최소 다른 쌍의 수를 구하세요. 입력 N(참석자의 수, 1 s,m.insert({s,p--}); for(i=0;i>s; a+=q(m[s]); u(m[s]); } cout