전체 글
-
[18268] Cow GymnasticsBOJ 2022. 3. 22. 23:19
https://www.acmicpc.net/problem/18268 18268번: Cow Gymnastics The consistent pairs of cows are $(1,4)$, $(2,4)$, $(3,4)$, and $(1,3)$. www.acmicpc.net 단순히 브루트포스하게 구현하면 되는 문제, find(v.begin(), v.end(), tar)-v.begin()로 tar가 발견된 인덱스를 얻는다. #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..
-
[1949] 우수 마을BOJ 2022. 3. 22. 23:16
https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 1의 조건을 만족시키면 3의 조건은 자연스레 만족하게 된다. 현재 마을이 우수마을인경우, 그 하위 노드는 항상 우수마을이 아니도록 진행하고, 현재 마을이 우수마을이 아닌 경우, 2가지 모두로 분기한다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool loca..
-
[18265] MooBuzzBOJ 2022. 3. 22. 23:13
https://www.acmicpc.net/problem/18265 18265번: MooBuzz Farmer John's cows have recently become fans of playing a simple number game called "FizzBuzz". The rules of the game are simple: standing in a circle, the cows sequentially count upward from one, each cow saying a single number when it is her turn. If a c www.acmicpc.net 함수 f(x)가 x번째까지 게임을 진행했을때, 숫자의 등장 횟수를 return 한다고 생각해보면, 선형에 불가능하니 이분탐색으로..
-
[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명을 제거하는 오류가 일어난다. (두번째 궁수도 왼쪽 아래를 노..