BOJ
-
[6359] 만취한 상범BOJ 2022. 2. 26. 09:39
https://www.acmicpc.net/problem/6359 6359번: 만취한 상범 한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다. www.acmicpc.net 2중 for로 일일히 토글하면서 시뮬레이션했다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; int t, n, a[105]; int main(void) { if (!local) ios_base::sync_with_stdio(0), cin.tie(0); cin >>..
-
[1727] 커플 만들기BOJ 2022. 2. 25. 10:31
https://www.acmicpc.net/problem/1727 1727번: 커플 만들기 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다. www.acmicpc.net 점화식은 매우 간단한데, 정렬하고 dp를 돌린다는 발상이 쉽게 떠오르지 않는다. 현재 (i, j)를 매칭하는 경우 / i를 스킵하는 경우 / j를 스킵하는 경우, 총 3가지로 분기해도 되지만, n> m; S = min(n, m); a.resize(n); b.resize(m); for (i = 0; i > a[i]; for (i = 0; i > b[i]; sort(a.begin(), a...
-
[13904] 과제BOJ 2022. 2. 25. 09:10
https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net vector에 입력된 것을 정렬한 뒤에, 일단 큐에 넣는다. v[i].first보다 큐의 size가 더 크다면, 현재까지 선택한 과제중 가장 점수가 낮을것을 포기한다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi =..
-
[1455] 뒤집기 IIBOJ 2022. 2. 24. 19:31
https://www.acmicpc.net/problem/1455 1455번: 뒤집기 II 세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다. 동전의 앞면을 0이라고 하고 뒷면을 1이라고 www.acmicpc.net 오른쪽 아래부터 동전을 뒤집어주면 더이상 toggle될 필요가 없으면서 앞면인, 완성된 영역을 늘려나갈 수 있다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pa..
-
[16120] PPAPBOJ 2022. 2. 24. 19:12
https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 문자열을 하나씩 확인하면서, P라면 스택에 넣는다. A라면, A의 다음것이 P이면서 스택의 size()가 2개 이상이면, PPAP를 만들 수 있으므로 PPAP를 만든다. 만약 불가능하면 NP를 출력하고, 루프가 끝난 뒤 스택의 size()가 1이하일때 PPAP로 판별할 수 있다. 결국 스택에 넣게 되는 문자는 P밖에 없으므로, 스택이 아니라 스택의 size()만을 의미하는 변수 하나로 관리해도 된다. 올바른 괄호 문자열을 판별할때와 비슷한 방식이 ..
-
[3991] 한번 쏘면 멈출 수 없어BOJ 2022. 2. 23. 18:30
https://www.acmicpc.net/problem/3991 3991번: 한번 쏘면 멈출 수 없어 은기는 모바일 게임 개발자이다. 이번에 은기가 만드는 게임은 Chain Shot! 게임 (SameGame, Jawbreaker, Bubble Shot, ... 으로도 알려져 있다)을 응용한 "한번 쏘면 멈출 수 없어" 이다. 게임은 직사각형 게임 www.acmicpc.net 가장 왼쪽 아래부터 차곡차곡 담아주면 된다. 이전색이 정확히 임의의 열에서(0행에서) 끝나든, 다음 열의 어느 행에서 끝나든 관계없이 색의 순서대로 플레이어가 선택한다면, 항상 최고점 획득이 가능함을 알 수 있다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool l..
-
[21554] 마법의 돌 장난감BOJ 2022. 2. 22. 20:34
https://www.acmicpc.net/problem/21554 21554번: 마법의 돌 장난감 만약 100번 이하의 ‘조작’으로 장난감을 정렬하는 것이 불가능하다면, $-1$을 출력하고 프로그램을 종료합니다. 만약 장난감을 정렬하는 것이 가능하다면, 첫 줄에는 ‘조작’의 횟수 $Q$를 출 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; int n; vector v; vector ans; in..
-
[2445] 별 찍기 - 8BOJ 2022. 2. 22. 20:28
https://www.acmicpc.net/problem/2445 2445번: 별 찍기 - 8 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 가장 왼쪽편에 있는 *만 보면, n개의 줄에 1..n개의 *을 찍는 규칙에, 좌우대칭/상하대칭을 이용했음을 알 수 있다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; vector ans; int main(void) { if (!local) ios_base::sync_with_stdio(..
-
[20291] 파일 정리BOJ 2022. 2. 22. 17:13
https://www.acmicpc.net/problem/20291 20291번: 파일 정리 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 www.acmicpc.net 파싱은 find('.')이 return한 iterator의 다음것부터 취해주면 된다. 입력에서 확장자를 파싱한 다음에, multiset에 하나를 넣고 set에 하나를 넣는다고 생각하자. 기본적인 구현은 multiset으로 충분하나, 출력조건을 맞춰주기 위해서 중복을 허용/비허용하는 자료구조를 동시에 썼다. #include using namespace std; #ifdef ONLINE_JUDGE const..
-
[10728] XOR삼형제 1BOJ 2022. 2. 21. 09:40
https://www.acmicpc.net/problem/10728 10728번: XOR삼형제 1 (위에서 아래로, 오른쪽에서 왼쪽으로 읽어주세요.) www.acmicpc.net n이 20이면 완전탐색이 가능하다. next_permutation()으로 모든 경우를 만들어주고, N^3으로 조건을 만족하는지를 판별한다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; int n; bool f(const vector& v) { int i, j, k; for (i = 0; i..