기로에 서다

문제 www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이�� www.acmicpc.net 문제 풀이 1. 두 점을 연결하는 비용은 각 x, y, z좌표끼리 차의 최소 값이므로 N개의 행성을 연결하려면 좌표끼리의 차를 값으로 가지는 N - 1개의 간선을 찾아야 합니다. 2. 이는 아래의 관찰을 통해 각 축에 대해서 좌표를 정렬했을 때 인접한 점들의 차만 간선에 추가하는 방법을 통해 해결했습니다. 서로 인접한 세 점 A, B, C에 대해 모든 점을 연결할 때, ..

문제 www.acmicpc.net/problem/12107 12107번: 약수 지우기 게임 1 N=4인 경우, A는 처음에 4,2,1을 지운다. 칠판에 남은 수는 3으로, B는 3을 지울 수밖에 없어 패배한다. www.acmicpc.net 문제 풀이 모든 수의 약수인 1을 제외한 N-1개의 수로 게임을 진행했을 때의 결과로 N개의 수를 뽑는 상황을 생각해보면 아래와 같습니다. 1. N - 1개의 수로 게임했고, 마지막 순서가 상대(B)에게 갈 때 A가 처음 뽑은 수의 약수에 1을 포함한다면 똑같이 마지막 순서가 상대에게 가므로 (A)승리 2. N - 1개의 수로 게임했고, 마지막 순서가 나(A)에게 올 때 A가 처음 순서에 1만 집고 시작하면 마지막 순서가 상대에게 가므로 (A)승리 3. 따라서 N이 1..

문제 www.acmicpc.net/problem/15927 15927번: 회문은 회문아니야!! 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 www.acmicpc.net 문제 풀이 1. 문자열이 팰린드롬이 아닌 경우) 문자열 그 자체가 팰린드롬이 아닌 가장 긴 부분 문자열의 길이이므로 그 길이를 출력하면 됩니다. 2. 문자열이 팰린드롬인 경우) 일반적인 팰린드롬의 성질에 대해서 생각해볼 때, 문자열의 시작과 끝 중에서 한 글자만 빠져도 팰린드롬이 깨진 다는 걸 알 수 있습니다. 모든 문자가 같은 문자열일 경우 모든 부분문자열에 대해 각 ..