분류 전체보기
-
[1976] 여행 가자BOJ 2022. 3. 2. 01:13
https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 같은 도시를 여러 번 방문이 가능하다는 조건에 의해서, "[1717] 집합의 표현"과 거의 동일한 문제가 되었다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair..
-
유니온파인드템플릿 2022. 2. 28. 19:02
base : https://www.acmicpc.net/problem/1717 처음에 memset(-1)을 해두고, p[i]의 절대값이 집합의 원소의 개수가 되도록 구현했다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; class UF { public: vector p; UF(int n) { p = vector(n + 1, -1); } int find(int cur) { if (p[cur] n >> m; int i; auto uf = UF(n); for (i = 0..
-
[2696] 중앙값 구하기BOJ 2022. 2. 27. 10:42
https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 중앙값을 포함하는 최소힙, 최소힙에 담기지 않는것들을 전부 넣는 최대힙 두개를 사용하는 잘 알려진 문제 수열이 정렬되었을때, 중앙값이상과 미만으로 두 힙을 넣는다고 생각하면 편하다. 하나씩 넣고, 균형을 잡아주면, 두 우선순위큐의 size가 동일하거나, 중앙값을 포함하는 큐의 size가 하나 더 많다. 동일할때에는 중앙값을 포함하는 힙에 넣고, 그렇지 않으면 반대쪽에 ..
-
[5052] 전화번호 목록BOJ 2022. 2. 27. 10:35
https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 입력된 전화번호를 전부 set에 넣는다. set을 전부 순회하는 첫번째 for(i)에 대해서, i의 다음것부터 substring끼리 비교해주었다. else if (cur > t; while (t--) { int n; cin >> n; st.clear(); int i; bool flag = true; for (i = 0; i > s; st.insert(s); } for (au..
-
[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..