BOJ
-
[2665] 미로만들기BOJ 2022. 3. 22. 23:09
https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 맵이 작으므로 종료상태일때 바로 return하지 않도록 구현해도 된다. 마냥 방문만 할수 없으므로, [행][열][벽을 지난 회수]로 방문처리해주었다. 위 방법은 입력이 충분히 작기에 가능하다. 실제로는 0-1 bfs태그가 달려야할거 같은 문제였다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #els..
-
[10282] 해킹BOJ 2022. 3. 22. 22:57
https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net B->A로 가는 간선을 이어준뒤, 해킹된 컴퓨터를 시작으로 다익스트라를 돌린다 dst[]에서 INF가 아닌 원소의 개수가 곧 찾아야 하는 첫번째 답이고, dst[i] bool { return A.cost > B.cost; }; priority_queue q(cmp); q.push({s, 0}); fill(dst, dst + MAX_N + 1, INF); dst[s] = 0; while (!q.empt..
-
[2447] 별 찍기 - 10BOJ 2022. 3. 18. 19:50
https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 매번 size를 1/3로 줄이고, 구간을 9개로 나누어서 재귀적으로 별을 찍자 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; cha..
-
[14425] 문자열 집합BOJ 2022. 3. 15. 06:44
https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net set에 n개를 넣고, m개의 string에 대해 (set.count()==1)를 누적한다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi ..
-
[1445] 일요일 아침의 데이트BOJ 2022. 3. 13. 02:54
https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 입력된 맵을 기준으로, 'g'가 놓인칸은 10000, 'g'가 인접해있는 칸은 1, 그외에는 0으로 가중치 배열을 갱신해둔다. 2차원 배열을 1차원 index로 바꾸고, 가중치 배열을 이용해 그래프를 만들어주고, 다익스트라를 돌린다. 최종 cost를 10000으로 나눈 몫이 쓰레기를 지나는 경우의 수이고, 10000으로 나눈 나머지가 쓰레기 옆을 지나는 경우. #inc..
-
[2304] 창고 다각형BOJ 2022. 3. 12. 20:45
https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 가장 큰 기둥을 기준으로 왼쪽, 오른쪽으로 나눈다. 오목한 부분이 있으면 안되므로, 나누어진 두개의 공간에서는 지붕이 높아지는 경우만 고려하면 되겠다. 가장 큰 기둥이 여러개 있는 경우에는 가장 큰 기둥의 최소 인덱스와 최대 인덱스를 알고있어야 한다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = ..
-
[17135] 캐슬 디펜스BOJ 2022. 3. 12. 04:48
https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 같은 턴에서, 3번의 공격을 한번에 진행해주어야 한다. 만약 순차적으로 공격할 경우, D=2일때 아래의 경우에서 0이 빈칸, 1이 적, 2가 궁수라고 보면 0 1 1 0 2 2 1번째 턴에서는 두 궁수가 모두 왼쪽 아래에 존재하는 적을 노리게 되도록 시뮬레이션이 되어야 하나 왼쪽의 궁수부터 적을 찾고, 해당 적을 제거해버리면 1번째 턴에 적을 2명을 제거하는 오류가 일어난다. (두번째 궁수도 왼쪽 아래를 노..
-
[7453] 합이 0인 네 정수BOJ 2022. 3. 12. 04:39
https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net O(N^4)는 시간 초과가 나오지만, O(2*(N^2))은 통과할 수 있는 수준이다. '중간에서 만나기'와 비슷한 방식으로, 4개의 집합 A, B, C, D를 2개의 집합 A+B, C+D로 나누어 투포인터를 할 수 있다. 다른 방법으로는 A+B에서 나올 수 있는 값을 전부 저장해두고 C와 D의 2중 루프에서 -(c+d)를 이분탐색할 수 있다. 모든 경우의 수를 탐색하기 위해서, ..
-
[2281] 데스노트BOJ 2022. 3. 12. 04:32
https://www.acmicpc.net/problem/2281 2281번: 데스노트 첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m www.acmicpc.net dp(i, j) = i번째 이름의 마지막 문자가 j번째 열에서 끝났을때의 최적해로 놓고, i번째 이름을 새로운 행에 쓰는 경우는 항상 고려하며, i번째 이름을 기존의 행에 이어서 쓰는 경우에는, (남은 칸)+(i번째 이름의 길이)= n) return 0; if (dp[i][c] != -1) return dp[i][c]; if (c == m + 1) return f(..
-
[2002] 추월BOJ 2022. 3. 9. 23:58
https://www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 터널에서 나온 차량번호를 기준으로 볼때, 현재 차량보다 더 늦게나온 차량이 터널에 더 먼저 진입한 경우를 확인한다. 터널에 나온 시점을 map로 관리하자. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using..