나그네

1865번: 웜홀 문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 어느 시작점에서 다시 시작 지점으로 돌아올 때 시간이 되돌아갈 수 있는지 여부를 구하는 문제다. 벨만 포드 알고리즘을 사용해 풀 수 있다. 도로는 양방향이지만 웜홀은 단방향임을 주의해야 한다. 처음엔 dist[1] < 0 이면 YES를 출력하도록 했다. 그러나 2%틀을 받고 모든 정점에서 다 해보는 코드를 짰는데 90% 언저리에서 시간초과가 났다. 결국 벨..

11657번: 타임머신 문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 그래프에서 1번 정점으로부터 각 정점으로의 최단 거리를 구하는 문제다. 가중치가 음수도 가능하므로 기본적인 벨만-포드 알고리즘으로 풀 수 있는 문제. 만약 무한정 작아질 수 있는 루프가 있으면 -1을 출력하면 된다. 코드 #include using namespace std; #define INF 1e18..

1016번: 제곱 ㄴㄴ 수 문제 https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 풀이 min 이상 max 이하의 제곱 ㄴㄴ 수의 개수를 구하는 문제다. 제곱 ㄴㄴ 수란 어느 제곱수로 나누어 떨어지지 않는 수를 말한다. 이 문제의 핵심은 에라토스테네스의 체의 변형이다. 1 ≤ min ≤ 1,000,000,000,000 min ≤ max ≤ min + 1,000,000 위와 같은 범위 때문에 애를 먹었다. 아래 범위 조건 때문에 0..

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 문제 https://www.acmicpc.net/problem/9694 9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다 맨위 첫 번째 줄에 T(1 b로 이동했다면 bef[b] = a 형태로 저장하고 다익스트라 알고리즘이 끝난 후 bef[M-1]부터 역으로 돌아가며 경로를 찾아낸다. 비슷한 문제로 [11779 최소비용 구하기 2 문제] | [11779 최소비용 구하기 2 해설]가 있다. 코드 #include using namespace std; #define INF 1000000000 int T, N, M; vector graph[20]; // [정점][다음 정점, 거리] vector dist(20, INF), visited(20, 0)..

2307번: 도로검문 문제 https://www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리 www.acmicpc.net 풀이 어느 한 간선을 차단하여 1에서 N까지 최단 경로가 얼마나 거리를 늘릴 수 있는지 구하는 문제다. 다익스트라 알고리즘으로 해결할 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 이 문제에서 중요한 것은 최단 경로 이외엔 차단할 필요가 없다. 왜냐하면 어차피 최단 경로로 지나가면 그만이기 때문이다. 그럼 먼저 ..

1545번: 안티 팰린드롬 문제 https://www.acmicpc.net/problem/1545 1545번: 안티 팰린드롬 만약 어떤 문자열 P가 있을 때, P[i]와 P[n-i-1] (0 ≤ i

14284번: 간선 이어가기 2 문제 https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 풀이 여러 정점 중 두 정점이 연결될 때 간선의 가중치가 최소가 되는 값을 구하는 것이므로 기본적인 다익스트라 알고리즘을 사용해 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자. [다익스트라 알고리즘 알아보기] 코드 #include using namespace std; #define INF 2147483647 int mai..

27497번: 알파벳 블록 문제 https://www.acmicpc.net/problem/27497 27497번: 알파벳 블록 첫째 줄에 버튼을 누른 횟수 $N$이 주어진다. $(1 \leq N \leq 1\,000\,000)$ 둘째 줄부터 $N$개의 줄에는 버튼을 누른 순서대로 누른 버튼에 대한 정보를 주며 아래와 같은 형식으로 주어진다. 1 c : 문자열 www.acmicpc.net 풀이 덱의 기본적인 쿼리를 사용하는 문제다. 가장 마지막에 추가한 수가 덱의 앞인지 뒤인지 판단하기 위해 스택을 만들어 하나씩 pop 하며 판단했다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); deque ..

27496번: 발머의 피크 이론 문제 https://www.acmicpc.net/problem/27496 27496번: 발머의 피크 이론 각 시간에 따른 혈중 알코올 농도는 {0.045, 0.089, 0.133, 0.131, 0.127}이다. 따라서 지금으로부터 2시간 후와 3시간 후, 총 두 시간 동안 혈중 알코올 농도를 유지할 수 있다. www.acmicpc.net 풀이 대회 때 누적합으로 풀었다가 빼는 배열의 크기를 제한하기 어려웠다. 그래서 그냥 더하다면서 배열에 더한 값을 저장하고 시간이 지속 시간보다 커지면 차례대로 빼가면서 범위를 만족하는지 확인했다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin...

27495번: 만다라트 만들기 문제 https://www.acmicpc.net/problem/27495 27495번: 만다라트 만들기 1번째 줄에는 “#x. “를 출력한 다음, 사전순으로 가장 먼저 오는 중간 목표를 출력한다. 숫자가 알파벳보다 사전순으로 먼저 오고, 알파벳 대문자가 알파벳 소문자보다 사전순으로 먼저 온다. 2 www.acmicpc.net 풀이 배열에서 (1,1), (1,4), (1,7), (4,1), (4,7), (7,1), (7,4), (7,7) 8점의 좌표와 문자열을 문자열 사전순으로 정렬하고 좌표를 (x, y)라고 한다면 (x-1, y-1)부터 (x+1, y+1)까지 (x, y)를 제외한 값을 또다시 정렬해 차례대로 출력하면 된다. 출력 형식만 잘 지켜서 구현하면 된다. 코드 #i..