전체 글
-
[1107] 리모컨BOJ 2022. 4. 25. 00:42
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 적당히 큰 범위를 잡아서, 고장난 버튼이 없어서 그 채널로 숫자를 입력해서 이동이 가능할때 그 채널의 자리수의 개수(string.length())와, 그 채널에서 n까지 가기 위해 필요한 +, -의 횟수(abs(n - i))를 최소로 갱신 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; ..
-
[14500] 테트로미노BOJ 2022. 4. 22. 15:32
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 일자형만 제외하면 3*2의 직사각형에서 2개만 제외하여 만들 수 있다. 일자형은 별도로 계산하고, 직사각형에서 2개씩 빼준 값을 업데이트 하는 방식으로 구현했다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll =..
-
[3584] 가장 가까운 공통 조상BOJ 2022. 4. 15. 15:59
https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 루트만 찾아서 lca로 구했다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; constexpr int M..
-
[12789] 도키도키 간식드리미BOJ 2022. 4. 12. 11:04
https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net tar = 1로 놓고, 현재 값==tar이면 tar를 증가시키고, stack.top()!=tar일때까지 간식을 먼저 받는다. 현재 값이 tar가 아닐때에는 전부 스택에 넣고, 마지막에 한번 더 stack.top()!=tar인 경우를 체크해서 "Sad"를 판 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false..
-
[3787] Count on CantonBOJ 2022. 4. 9. 17:19
https://www.acmicpc.net/problem/3787 3787번: Count on Canton One of the famous proofs of modern mathematics is Georg Cantor's demonstration that the set of rational numbers is enumerable. The proof works by using an explicit enumeration of rational numbers as shown in the diagram below. 1/1 1/2 1/3 1/4 1/5 ... 2/1 2 www.acmicpc.net 짝수행이냐 홀수행이냐에 의해 거슬러 올라가거나, 내려가야 한다. 같은 행에서는 분모와 분자의 절대값의 합이 동일하니,..
-
[5525] IOIOIBOJ 2022. 4. 7. 04:18
https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 선형에 풀기 위해서는 단순히 substr을 비교하는것이 아니라, 현재까지 확인한 IOIOI...문자열의 길이를 저장해야한다. 올바른 괄호를 판별하는 스택문제와 유사하다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else cons..
-
[9375] 패션왕 신해빈BOJ 2022. 4. 7. 03:50
https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 선택하지 않는 경우까지 생각해서 항상 종류별 원소의 개수+1을 곱하고 모든 집합에서 아무것도 선택하지 않은 경우만 빼준다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool l..
-
[18111] 마인크래프트BOJ 2022. 4. 3. 18:28
https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 입력된 블럭들중 가장 작은것부터, 가장 큰것까지만 탐색하면 그안에 항상 최적해가 있음을 기대할 수 있다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; co..
-
[1302] 베스트셀러BOJ 2022. 4. 1. 16:32
https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net multiset에 전부 넣고, 순회하면서 count()가 크거나, count()가 동일하며 사전순으로 앞서있을때 갱신한다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using ..
-
[1940] 주몽BOJ 2022. 3. 30. 02:40
https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 배열에 개수를 기록해두고, a[i]와 a[m-i]의 최소값만큼 갑옷을 만들 수 있다. i==(m - i)인 경우에는 2개씩 사용하므로, 이에 대한 예외처리에 주의할 필요가 있다. 배열을 천만개 잡고, 천만번 i를 돌려도 되지만, m>200'000인 경우에는 어처피 항상 만들 수 있는 갑옷이 없고, 양쪽에서 좁혀오듯 확인하며, 어처피 순열이 아니라 조합에 가까우니 m/2만 ..