분류 전체보기
-
[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..
-
[4991] 로봇 청소기BOJ 2022. 2. 21. 07:28
https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net "[17244] 아맞다우산"과 거의 동일한 문제다. 방문처리를 (행, 열, 비트)로 두고, 비트에 S개의 쓰레기를 처리한 여부를 [0, 1> m >> n; if (m == 0 && n == 0) break; memset(a, 0, sizeof(a)); S = 0; int i, j, sy, sx; for (i = 0; i a[i][j]; if (a[i][j] == 'o') { sy = i, sx = j; a..
-
[13911] 집 구하기BOJ 2022. 2. 20. 11:34
https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 시작 지점이 여러개인 다익스트라를 맥도날드/스타벅스에 대해 두번 돌려준다. 하나의 다익스트라가 끝나면, 거리를 맥세권/스세권인 경우에는 그대로 유지하고, 그렇지 않을때 INF로 바꿔둔다. 두번에 걸친 다익스트라가 끝나면, 각 다익스트라에서 구한 dst1[i]+dst2[i]의 최소를 찾으면 된다. 맥도날드나 스타벅스가 존재하는 정점은 dst1[i..
-
[3020] 개똥벌레BOJ 2022. 2. 20. 11:27
https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 만약 N과 H가 조금만 작았더라면, 단순히 앞뒤를 뒤집은 석순과 종유석의 높이의 기준만 잘 설정해주어 선형탐색으로 풀 수 있었을 것이다. 어처피 데이터의 순서가 무의미하니, 석순과 종유석이 정렬되었다고 가정하고 시작해보면, 어떤 하나의 높이 i에 대해서, lower_bound(i) 이전의 장애물은 파괴할 필요가 없는 장애물이고, lower_bound(i) 이후의 장애물은 모두 파괴해야 하는 장애물이 ..
-
[10252] 그리드 그래프BOJ 2022. 2. 19. 08:11
https://www.acmicpc.net/problem/10252 10252번: 그리드 그래프 m × n 직사각 그리드(rectangular grid)는, x-좌표의 범위가 0부터 n-1까지인 정수이고 y-좌표의 범위가 0부터 m-1까지 정수인 평면상의 점들에 대응하는 정점들을 가지고, 두 정점에 대응하는 두 점 사이 www.acmicpc.net 일단 (0, 0)에서 맨 윗줄과 맨 오른줄을 순회하고 시작한다. 행이 홀수라면 단순히 원형으로 연결된 간선을 밟지않고 지날 수 없으므로, 1회는 원형간선을 거쳐야한다. (n-1, m-1)에서 (n-1, 0)으로 간 다음에는, 다시 인접한 간선만 밟아 올라갈 수 있다. 행이 짝수라면 더욱 간단히, 원형간선을 밟지 않아도 된다. 모든 과정에서, 지나가는 열의 번호..
-
[13164] 행복 유치원BOJ 2022. 2. 17. 23:39
https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 입력된 수열에서 인접간 수의 차를 큐에 넣고, m-1개만큼 가장 큰것을 제외한다. 이후 큐에 남은 원소의 합이 곧 정답이 되겠다. #include using namespace std; using ll = long long; ll n, m, ans; vector a; priority_queue q; int main(void) { ios_base::sync_with_stdio(..
-