전체 글

2644 - 촌수계산https://www.acmicpc.net/problem/2644문제부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산ex, 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌/ 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌=> 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램?입력사람들은 1, 2, 3, ..., n (1 첫째 줄: 전체 사람의 수 n둘째 줄: 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어짐셋째 줄: 부모 자식들 간의 관계 개수 m넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x, y (x는 y의 부모 번호)각 사람의 부모는 최대 한 명만 주어짐출..

12851 - 숨바꼭질 2https://www.acmicpc.net/problem/12851문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈: 현재 점 N에 있고, 동생은 점 K에 있다.수빈이의 위치가 x일 때 걷는 경우: 1초 후, x - 1 or x + 1 위치로 이동 / 순간이동 하는 경우: 1초 후 2 * x 위치로 이동=> 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지, 가장 빠른 시간으로 찾는 방법이 몇 가지인지 구하는 프로그램입력: N (0 출력동생을 찾는 가장 빠른 시간가장 빠른 시간으로 동생을 찾는 방법의 수풀이`time[i]`: i번 위치까지 도달하는 데 걸린 최소 시간`cnt[i]`: i번 위치에 최소 시간으로 도달하는 방법의 수`A..

2098 - 외판원 순회https://www.acmicpc.net/problem/2098문제1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다 (길이 없을 수도 있음)한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다(단, 한 번 갔던 도시는 다시 갈 수 없음, 맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외)이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우려고 함각 도시간에 이동하는데 드는 비용: W[i][j] 도시 i에서 도시 j로 가기 위한 비용 (대칭적 X, W[i][j]는 W[j][j]와 다를 수 있음) 모든 도시간의 비용은 양의 정수, W[i][..

1146 - 지그재그 서기https://www.acmicpc.net/problem/1146문제N명의 학생들을 줄을 세우려고 함1. 맨 앞줄: 아무나2. 둘째 줄: 아무나3. 셋째 줄: 첫째 줄에 서 있는 사람 둘째 줄에 서 있는 사람 > 셋째 줄에 서 있는 사람/ 첫째 줄에 서 있는 사람 > 둘째 줄에 서 있는 사람 -> 둘째 줄에 서 있는 사람 4. 넷째 줄부터는 둘째 줄과 셋째 줄 비교 => N번째 줄은 N-2번째 줄과 N-1번째 줄 비교ex. 1이 가장 작은 사람, N이 가장 큰 사람(같은 키 X) => 13254 / 32514=> 총 몇가지 경우의 수?입력: 학생 수 N (1 출력: 총 경우의 수 % 1,000,000 나눈 나머지풀이지그재그 수열: a1 a3 a5 a2 a4 ... 파스..

16930 - 달리기https://www.acmicpc.net/problem/16930문제다이어트를 위해 NxM 크기의 체육관을 달림체육관은 1x1 크기의 칸으로 나뉘어져 있고, 칸은 빈 칸 or 벽/ (x, y): x행 y열에 있는 칸 매 초마다 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향 하나 고르고, 그 방향으로 최소 1개, 최대 K개의 빈칸 이동=> 시작점 (x1, y1), 도착점(x2, y2) 주어졌을 때, 시작점에서 도착점으로 이동하는 최소 시간?입력첫째 줄: 체육관의 크기 N과 M, 1초에 이동할 수 있는 칸의 최대 개수 K둘째 줄 ~ N개의 줄: 체육관의 상태/ 빈 칸: '.', 벽: '#'마지막 줄: 네 정수 x1, y1, x2, y2 -> 두 칸은 서로 다른 칸이고 항상 빈 칸출력(x..

2110 - 공유기 설치https://www.acmicpc.net/problem/2110문제도현이의 집 N개가 수직선 위에 있고 각각의 집의 좌표는 $X_1$, ..., $X_N$집 여러 개가 같은 좌표를 가지는 일 X언제 어디서나 와이파이 즐기기 위해 공유기 C개 설치하려고 함/ 최대한 많은 곳에서 와이파이 사용하려고 함 -> 한 집에는 공유기 하나만 설치 O, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 함=> C개의 공유기 N개의 집에 적당히 설치 -> 가장 인접한 두 공유기 사이의 거리 최대입력첫째 줄: 집의 개수 N (2 둘째 줄부터 N개의 줄: 집의 좌표 $x_i$ (0 출력: 가장 인접한 두 공유기 사이의 최대 거리풀이이진 탐색(Binary Search)정렬된 데이터에서..