https://www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net 각각의 위치에서 시작해서 만들어지는 문자열을 map result에 문자열과 문자열이 만들어지는 횟수도 세어가며 저장을 해서 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int n, m, k; vector board; vector like; map result; int dxdy[8][2] = { {0,-1},{-1,0},{0,1},{1,0},{-1,-1},{-1,1},{1,1},{1,-1..

https://www.acmicpc.net/problem/18235 18235번: 지금 만나러 갑니다 첫 번째 줄에 세 정수 N, A, B가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ A, B ≤ N, A ≠ B) www.acmicpc.net discovered[500001][2][20]; //[위치][오리:0, 육리:1][몇일차인지] = 방문여부 를 이용하여 너비 우선 탐색을 통해 문제를 해결했다. 코드 #include #include #include #include #include #include using namespace std; int n, a, b; int discovered[500001][2][20]; //[위치][오리:0, 육리:1][몇일차인지] = 방문여부 queue q; //(위..

https://www.acmicpc.net/problem/10273 10273번: 고대 동굴 탐사 입력의 첫 줄엔 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 10) 각 테스트 케이스의 첫 줄엔 탐사할 수 있는 동굴의 수 N과 서로 직접 연결된 동굴 쌍의 수 E가 주어진다. (1 ≤ N ≤ 2 · 10 4; 0 ≤ E www.acmicpc.net 해당 위치에서 탐색을 하여 최대로 얻을 수 있는 이익을 cache에 저장하여 다이나믹 프로그래밍을 이용해 최대 이익을 찾고, cache에 저장된 값을 이용해서 최대 이익일 때 방문하는 동굴들을 찾아내서 문제를 해결했다. 코드 #include #include #include #include using namespace std; int max_int = nu..

https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net [위치][방문 지금까지 방문한 위치(비트로 표현)] = 최소비용을 저장하여 다익스트라 알고리즘을 이용해 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int n, k; vector adj[10]; int Solve(int start, int visited) { vector result(10, vec..

https://www.acmicpc.net/problem/21276 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 이름마다 번호를 매칭 시켜서 사용했다. x의 조상에는 y가 있다는 정보를 얻을 때마다, y에서 x로 가는 그래프를 만들고, x의 indegree를 증가시키면 indegree가 0인 것은 시조라는 것을 알 수 있으므로 이를 이용해 위상 정렬을 이용해서 문제를 해결했다. 코드 #include #include #include #include #include #include using nam..

https://www.acmicpc.net/problem/18128 18128번: 치삼이의 징검다리 건너기 첫 번째 줄에 땅의 크기 N(3 ≤ N ≤ 1,000), 물 생성지 개수 W(1 ≤ W ≤ N)가 주어진다. 두 번째 줄부터 W+1줄까지 물의 생성 위치 x(행), y(열) (1 ≤ x, y ≤ N)가 주어진다. W+2줄부터 N개의 줄에 www.acmicpc.net 각 위치에 물이 며칠에 차오르는지 표시하고, 이분 탐색을 이용해 도착점에 도달할 수 있는 가장 빠른 날짜를 계산하여 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int n, w; vector water; vector board; int wat..