BOJ
-
[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만 ..
-
[3649] 로봇 프로젝트BOJ 2022. 3. 30. 02:09
https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net s를 front()에, e를 back()에 놓고 sx이면 e--, 그 외에는 s++이다. 도중에 v[s] + v[e] == x인 순간이 한번이라도 발생하면, 해당 s, e는 abs(e - s)가 최대라는 조건을 자연스레 만족한다. 물론 그러한 경우가 한번도 존재하지 않았다면, danger를 출력하면 된다. #include using namespace std; #ifdef ..
-
[2458] 키 순서BOJ 2022. 3. 29. 00:18
https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 현재 정점이 자신의 키가 몇번째인지를 알수 있는가는, 플로이드를 이용해서 dst를 구한 뒤 현재 정점을 제외한 모든 정점이, 현재 정점에서 다른 정점으로 도달 가능 하거나(dst[cur][i] < INF) 다른 정점에서 현재 정점으로 도달 가능해야 한다. (dst[i][cur] < INF) 아이디어는 골4치곤 좀 어려운 느낌이다. 플로이드 태그는 스탠다드 난이도가 없어서 난이도 매기기가 애매한듯 싶..
-
[9370] 미확인 도착지BOJ 2022. 3. 29. 00:10
https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이는 크게 2가지가 가능한데, 구간을 잘라서 다익스트라를 그대로 여러번 돌리는 방법이 있고 그래프를 적절히 조작하여 "[1445] 일요일 아침의 데이트"처럼 푸는 방법이 있다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endi..