전체 글
-
[1774] 우주신과의 교감BOJ 2022. 1. 15. 23:33
https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 이미 연결된 간선 가중치테이블의 값을 0으로 설정해둔다. 모든 (i, j)에 대해서, 두 점 사이의 거리를 가중치를 갖는 간선을 생성해주면 남는것은 mst를 구하는 일 밖에 없다. 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 31 32 33 34 35 36 37 38 39..
-
[1826] 연료 채우기BOJ 2022. 1. 15. 22:40
https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 도달할 수 있는 주유소의 연료를 전부 큐에 넣는다. 큐가 비었다는 것은, 도착지에 도다를 수 없음을 의미하니 -1을 출력하고 그렇지 않을때에는 충전할 수 있는 연료의 최대값만큼을 충전한다. int s;의 의미는 '현재까지의 연료의 총 량'이자, '갈 수 있는 주유소의 범위'다. 하나의 주유소에서 여러번 주유하는 일이 없도록, 22라인처럼 최악의 경우일때 선형으..
-
[2485] 가로수BOJ 2022. 1. 12. 21:46
https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 나무를 심는 길이는 크면 클수록 좋다. 인접한 가로수 사이의 간격을 전부 __gcd()를 가하면 나무를 심는게 가능하면서, 길이가 최대인 값을 찾을 수 있다. 이 값을 찾은 뒤에는, ((가장 큰 값)-(가장 작은 값))/(나무를 심는 간격)-n+1이 답이된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include using namespace std..
-
[1966] 프린터 큐BOJ 2022. 1. 12. 21:02
https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 제목부터 프린터 '큐'이지만, 사실 큐를 안 쓰고 vector로 정렬해도 풀릴 거 같고.. 정렬로 풀리니 우선순위 큐도 가능하겠다. 큐에 넣는 데이터를 pair로 넣어서 int는 입력되는 우선순위를 넣고, bool에는 현재 데이터가 탐색 대상인지를 포함시켜주었다. 우선순위의 상태를 나타내는 int[10]을 따로 저장하여, 현재 큐에 존재하는 우선순위들의 분포를 파악할 수 있게 한 뒤, 큐에서 하나 꺼..
-
[2805] 나무 자르기BOJ 2022. 1. 12. 20:30
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 절단기를 mid으로 설정했을 때 얻을 수 있는 나무의 길이를 리턴하는 함수를 구현했다면, 나무가 M보다 더 작게 잘렸다면 절단기의 높이를 낮추고, 반대로 리턴값이 M이상일 때에는 이를 정답으로 기록해두고, 절단기의 높이를 높인다. 초기 범위는 나무의 높이와도 같이 (0, 10억)으로 설정해주면 되겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 1..
-
[17141] 연구소 2BOJ 2022. 1. 9. 13:01
https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 바이러스를 놓은 시점부터 생각해보면, 단순한 level-based bfs를 돌려주면 된다. 정확한 명칭은 모르겠는데, turn이 바뀌는 시점을 일일히 bfs 안에서 체크할 필요가 없이, bfs에서 사용하던 while(!q.empty())안에 sz=q.size(), while(sz--)를 한번 더 중첩하여 간단하게 구현할 수 있다. 바이러스를 놓는 경우의 수는 최악의 경우에 10C5정도, V+E도 3000을..
-
[2116] 주사위 쌓기BOJ 2022. 1. 9. 12:55
https://www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 맨 아래가 정해지면 그 위 n-1개의 주사위의 순서는 필연이므로 dfs 하듯이 구현해줄 수 있다. 간단하게 생각해서, 한쪽면에 올 숫자는, 위아래와 맞닿는 면 2개를 제외한 4개중의 최대값을 선택한다. 주사위의 맞은편의 연결된 인덱스(?)가 조금 헷갈리는데, 한번에 base[]={5, 3, 4, 1, 2, 0};처럼 상수마냥 정의해두면 그나마 조금 덜 헷갈린다. 이제는 맨 아래를 놓는 경우의 수를 찾으..
-
[21740] 도도의 수학놀이BOJ 2022. 1. 8. 16:20
https://www.acmicpc.net/problem/21740 21740번: 도도의 수학놀이 길이가 N인 수열이 주어진다. 도도는 이 수열의 수를 이어붙여 180도 회전시켰을 때 가장 큰 수를 만들려고 한다. 각 숫자를 180도 회전시켰을 때 환원되는 숫자는 다음과 같다. $0$ -> $0$ $1$ -> $1$ $2$ www.acmicpc.net 정렬의 기준은 "[16496] 큰 수 만들기"와 마찬가지로 string의 '+'와 부등호를 통한 사전순 비교로 간단히 구현된다. 해당 문제와 달리, 180도 회전하는 부분에 대한 처리와 하나의 수를 추가 할 수 있다는 조건이 추가되었고, 회전에 대한 처리는 간단히 정렬 전과 후에 한번씩 돌려줄 수 있다. 추가할 수는 가장 길이(자리수)가 길면서, 가장 큰 ..
-
[21608] 상어 초등학교BOJ 2022. 1. 5. 14:37
https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 그냥 잘 구현하면 되는 문제라 별로 적을게 없다.. 모든 (y, x)에 대해 (인접한 칸에 좋아하는 학생 수)를 구해야 하는데, 현재 (i, j)에서의 값을 cnt에 넣었고 현재 시점까지의 최대 cnt를 curScore에 저장해두었다고 생각해보면, cntcurScore인 경우에는 기존 모든 후보지를 clear()해주고 현재 위치를 추가하면 된다. 위 3가지 경우를 잘 나누어 주는게 이 ..