BOJ
-
[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(..
-
[1120] 문자열BOJ 2022. 2. 14. 17:40
https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 남는 자리는 그리디적으로 Y와 같은 문자로 채워준다고 가정하면, 채워주지 않고 X의 문자를 그대로 사용하는 구간만 탐색하면 된다. 문자열의 길이를 각각 A, B라 하면 하나는 항상 [0, A)까지 비교하고, 다른 문자열에서 [0, B-A]를 시작점으로 갖는 길이 A의 두 문자열을 비교하면 된다. #include using namespace std; strin..
-
[22115] 창영이와 커피BOJ 2022. 2. 13. 02:18
https://www.acmicpc.net/problem/22115 22115번: 창영이와 커피 커피는 종류별로 하나씩 준비되어 있기 때문에, 동일한 커피를 여러 개 마실 수 없음에 유의하라. www.acmicpc.net 가격이 전부 동일하다고 생각하면 되므로, 사실상 "[12865]평범한 배낭" 과 비슷하게 풀 수 있다. 가격이 1이라고 생각하고, 가격을 최소화하는 느낌으로 접근하자. #include using namespace std; constexpr int INF = INT_MAX >> 1; int n, k, dp[100001], w[101]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; int i, j; fi..
-
[16493] 최대 페이지 수BOJ 2022. 2. 12. 23:07
https://www.acmicpc.net/problem/16493 16493번: 최대 페이지 수 첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이 www.acmicpc.net 하나의 챕터를 중복해서 읽지 않는 문제이므로, 역방향으로 갱신하는 배낭문제로 풀 수 있다. #include using namespace std; int n, m, ans, dp[201], w[201], v[201]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; int i, j; ..
-
[12034] 김인천씨의 식료품가게 (Large)BOJ 2022. 2. 12. 22:50
https://www.acmicpc.net/problem/12034 12034번: 김인천씨의 식료품가게 (Large) 입력의 첫 번째 라인(줄)은 테스트 사례의 케이스의 수 T를 나타냅니다. 이후의 라인은 T개의 테스트 케이스가 이어집니다. 각 테스트 케이스는 두 줄로 구성됩니다. 첫 번째 줄에는 INU 식료품가 www.acmicpc.net n이 작으므로 (v[i]*4)/3 == v[j]를 만족하는 v[i]를 n^2으로 찾으면 된다. #include using namespace std; using ll = long long; ll n; vector v, ans; bool chk[201]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); ll T, ..
-
[2012] 등수 매기기BOJ 2022. 2. 12. 22:29
https://www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 정렬하고, 맨앞부터 1등..2등..3등..으로 매기면 된다. #include using namespace std; using ll = long long; ll ans, n; vector v; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; v.resize(n); ll i; for (i = 0; i > v[i]; sort(v.beg..