공작소

>> 문제 바로가기 (https://www.acmicpc.net/problem/25181) 풀이 과정 특정 i번째 숫자 앞뒤로, 바꿨을 때 Ai != Bj && Aj != Bi 를 만족하는 j번째 숫자를 찾아 바꾸면 된다. import sys input = sys.stdin.readline n = int(input().rstrip()) arr = list(map(int, input().rstrip().split())) narr = [] for a in arr: narr.append(a) done = True for i in range(n): if arr[i] == narr[i]: idx = i + 1 while idx < n and narr[i] == narr[idx]: idx += 1 if idx ==..

>> 문제 바로가기 (https://www.acmicpc.net/problem/25595) 문제 기아데 연방 공화국은 '레기온'이라는 인공지능 무인 병기들과 전쟁 중이다. 공화국은 레기온에 대항할 수단으로 '레긴레이브'라는 보행 병기를 개발했다. 공화국 군인들 중 소수정예는 이 레긴레이브에 탑승해서 레기온에 맞서 싸운다. 신에이 노우젠은 제 86 전략기동전단 기갑전대의 전대장이자 근접전의 대가이다. 그는 레기온들의 위치를 전부 파악할 수 있는 이능력이 있다. 그의 전투 스타일은 직접 레기온이 있는 위치 근처로 가서 빠르게 해치우는 것이다. 레긴레이브는 화력이 다소 떨어지지만, 기동성이 뛰어나다는 장점이 있기 때문이다. 레긴레이브는 대각선 네 방향으로 이동할 수 있다. 현재 좌표가 (r, c) 라면 (r−..

>> 문제 바로가기 (https://www.acmicpc.net/problem/29196) 문제 이 대회의 운영진 중 한 명인 KSA 학생은 얼마 전 소수 공포증을 극복했으나 또 다른 소수를 구별할 수 없게 되어 버렸다. KSA의 명예를 지키기 위해 어떤 소수 k를 입력받아 k를 나타내는 분수 p/q를 아무거나 구해주자. p와 q는 10^9 이하인 양의 정수이며, k와 p/q의 절대오차 또는 상대오차가 10^(−6) 이하면 정답이다. 입력 첫 번째 줄에 소수 k가 주어진다. 출력 첫 번째 줄에 조건을 만족하는 분수가 존재한다면 YES, 아니라면 NO를 출력한다. 만약 그러한 분수가 존재한다면, 두 번째 줄에 두 정수 p, q를 공백을 사이에 두고 출력한다. 정답이 여러 개 존재한다면 그중 아무거나 출력해..

>> 문제 바로가기 (https://www.acmicpc.net/problem/14675) 문제 그래프 이론에서 단절점(cut vertex)과 단절선(bridge)은 다음과 같이 정의 된다. 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다. 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 간선을 단절선이라 한다. 이 단절점과 단절선을 우리는 트리(tree)에서 구하려고 한다. 그래프 이론에서 트리(tree)의 정의는 다음과 같다. 트리(tree) : 사이클이 존재하지 않으며, 모든 정점이 연결되어 있는 그래프 트리의 정보와 질의가 주어질 때, 질의..

>> 문제 바로가기 (https://www.acmicpc.net/problem/31229) 문제 다음 조건을 만족하는 길이 N의 수열 A = {A_1, A_2,…,A_N}를 출력하시오. 1≤ i < j ≤ N을 만족하는 모든 정수 i와 j에 대해서 다음 조건을 만족한다. A_i != A_j이고 수열 A의 모든 원소는 1 이상 10^9 이하의 정수이다. A_i + A_j는 A_i × A_j의 약수가 아니다. 입력 첫째 줄에 수열 A의 길이를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 5 000) 출력 첫째 줄에 조건을 만족하는 수열 A의 원소들을 공백으로 구분하여 출력한다. 위 조건을 만족하는 수열이 여러 개라면 그중 아무거나 출력한다. 풀이 과정 위 조건을 만족하는 수열은 홀수 수열이다. 홀수와 홀수..

>> 문제 바로가기 (https://www.acmicpc.net/problem/16956) 문제 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다. 목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자. 입력 첫째 줄에 목장의 크기 R, C가 주어진다. 둘째 줄부터 R개의 줄에 목장의 상태가 주어진다. '.'는 빈 칸, 'S'는 양, 'W'는 늑대이다. 출력 늑대가 양이 있는 칸으로 갈 수 없게 할 ..