BOJ
-
[3687]성냥개비BOJ 2022. 1. 23. 09:25
https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 최대는 쉽다, "7111..."혹은 "111..."의 형태중 하나. 최소는 dp로 해결이 가능한데, 6은 원래는 0이지만, 첫자리에 0이 올 수 없으니 dp[6]은 6이다. 한마디로, dp의 초기값과 기저 사례(db)가 분리되어 있다는 뜻이다. 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 ..
-
[20057] 마법사 상어와 토네이도BOJ 2022. 1. 23. 09:22
https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 토네이도의 이동 방향은 '좌하우상'의 반복이고, 길이는 {1, 1, 2, 2, 3, 3...}같은 형태로, 2번마다 1씩 증가하는 형태이다. 문제에 제시된 '일정한 비율'을 db로 넣어준다. 해당 db는 회전의 용이성을 이유로 일부러 5*5의 형태로 잡아두었고 토네이도의 방향이 회전할때마다 db도 같이 회전시켜주었다. 소수점 아래를 버리는 부분은 int간의 '/'연..
-
[16208] 귀찮음BOJ 2022. 1. 17. 18:26
https://www.acmicpc.net/problem/16208 16208번: 귀찮음 현우는 무슨 이유에선지 길이 a1, ..., an의, 총 n개의 쇠막대가 필요해졌다. 하지만 그가 가진 것은 길이 a1+...+an의 하나의 쇠막대뿐이었다. 현우는 이 막대를 직접 잘라서 원래 필요하던 n개의 쇠 www.acmicpc.net 작은거부터 잘라서 막대를 만들어주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include using namespace std; using ll = long long; ll n, sum, ans; vector v; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0)..
-
[11444] 피보나치 수 6BOJ 2022. 1. 16. 00:21
https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net "[2749] 피보나치 수 3" 은 모듈러가 작아서 피사노주기를 이용해 꽤나 간단하게 해결이 가능했지만, 모듈러가 커지면 행렬의 거듭제곱으로 O(logN)의 복잡도를 갖는다. a^b mod c의 값을 logN만에 구하던 것과 매우 유사하다. 단지 수 하나가 2by2 행렬로 바뀐것 뿐이다. 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 ..
-
[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..