0과 1의 쉼터

풀이 'Six Degrees of Separations' theory로도 불리는 이론이다. 자신과는 아무 연관성(inf or V) 없는 사람일지라도, 만약 친구가 한 명 이상 있다면(connected), 대부분 6단계(5명의 관계)를 걸쳐 알 수 있게 된다는 이론이다. 즉, 당신이 6단계를 넘어선다면 아싸일 확률이 매우 높... 문제에서 "모든 사람은 친구 관계로 연결되어져 있다." 라고 하여 주어지는 TC에 대한 별도의 예외처리는 없다. Floyd Warshall을 이용해 모든 친구 관계에 대해서 최단 단계를 구해주고, 각각의 유저가 모든 유저간에 대한 단계의 합으로이루어진 집합(step) 속 최솟값의 순번을 구하자. 소스코드 소스코드 보기 출처 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의..

풀이 주어진 m, n으로 만들 수 있는 사각형의 테두리의 면적을 구해주면 된다. m과 n 중 하나가 2 이하인 경우에는 내부에 빈 면적이 없다는 점을 유의해서 정답을 출력해주자 소스코드 소스코드 보기 출처 27213번: Граничные клетки У Ани есть клетчатый листок бумаги, на котором она нарисовала прямоугольник размером $m \times n$. После этого она раскрасила клетки прямоугольн www.acmicpc.net

풀이 최대 200개의 아이스크림 중 3개로 이루어질 수 있는 조합의 개수만 세면 된다. N의 최대값이 작으므로 주어지는 입력을 그래프로 구현 후 모든 경우를 다 살펴보자. ban_list [n1] [n2] : (n1, n2) 조합의 불가능 여부 단, 섞어먹으면 안되는 조합이 항상 오른차순으로 주어진다는 보장이 없어 양방향 그래프로 구현하자. 3개의 조합을 선별해야 하므로 순서는 상관없다. 또한, 양방향 그래프이기 때문에 그리디 로직(먼저 고른 수는 나중에 고른 수보다 항상 작음)을 적용시킬 수 있다. 조건을 모두 만족 (조합이 성립)하는 경우에만 아이스크림 조합의 수를 증가시켜 주자. 소스코드 소스코드 보기 출처 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진..

풀이 주어진 수에 맞는 행과 열을 출력하면 된다. 8 x 8 크기이므로 다음처럼 8의 몫과 나머지의 특징을 이용해 쉽게 답을 구할 수 있다. (n - 1) % 8 의 나머지는 모든 n에 대해 0 ~ 7의 index와 같다. (n + 7) // 8 의 몫은 모든 n에 대한 " 8의 비 + 1 " 과 같다. 소스코드 소스코드 보기 출처 27239번: Шахматная доска Саша пронумеровала клетки шахматной доски, начиная с левого нижнего угла (клетки a1) по горизонталям сверху вниз, внутри горизонтали слева н www.acmicpc.net

풀이 방의 가로 / 세로 / 높이가 각 줄에 걸쳐서 입력으로 주어진다. 이때 문제에서 주어지는 조건을 만족하는 "좋은 방"인지 판별하면 된다. (가로와 세로 중 더 짧은 길이) / 높이 >= 2 (가로와 세로 중 더 긴 길이) / (가로와 세로 중 더 짧은 길이)

풀이 가희가 승강장 까지 내려가기 위한 수단(path)과 높이(height)를 제한에서 주어진 단위로 변환하여서 계산하면 된다. 계단이면 17cm, 에스컬레이터면 21cm이다. 주어진 모든 입력에 대해 단위를 곱하고, 총합을 출력하면 된다. 소스코드 소스코드 보기 출처 27880번: Gahui and Soongsil University station Soongsil University Station is famous as the deepest station on Seoul Subway Line 7. This station is so deep that the platform is on the B6. Gahui was surprised that she did not reach the platform afte..

풀이 수빈이가 동생한테 가는 방법은 현 위치(N)에 대해 3개의 방법(N + 1, N - 1, 2N)이 있다. 항상 N이 K에 가까워지는 방법이 정답이라는 보장이 없기 때문에 모든 경우에 대해 탐색을 해봐야 한다. Queue에 수빈이의 범위 내의 새로운 위치를 담아주고, 다시 꺼낼 때 이동 횟수를 기록한다. 단, 이미 방문한 위치를 재 방문할 때는 이동횟수가 같거나 크기 때문에 최소 이동횟수 기록을 보장하기 위해 방문하지 않은 경우에만 Queue에 담아두었다. Queue의 변화에 대해 궁금하다면 아래를 참고하자. 처음에 주어진 N(5)에 대한 3가지 이동 방법을 모두 기록하며, Queue에서 새로운 위치(nx)를 꺼낼때마다 이에 대한 이동 방법 또한 기록한다. 빨간색 대각선은 동일한 이동시간을 가진 위치..

풀이 배추흰지렁이는 인접한 배추(기준이 되는 배추로부터 상하좌우에 위치한 배추)로 퍼져나갈 수 있다. 따라서 인접한 배추들을 전부 탐색하고, visited에 탐색한 배추를 기록하고자 한다. 결국 인접한 배추들의 덩어리인 연결 요소(Connected Component)의 개수를 구하는 문제이다. 배추가 위치한 장소만을 탐색하기 위해 배추의 위치를 입력받을 때 배추의 위치를 location에 기록한 후, DFS의 시행횟수를 세어 풀이했다. 소스코드 소스코드 보기 출처 및 참고자료 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net

풀이 C(N, K)에 대해 N의 범위는 1 ~ 10, K의 범위는 0 ~ N이므로 단순 계산으로 풀이할 수 있다. C(N, K) = N! / (K! * (N - K)! N! = N * (N - 1) * (N - 2) * ... * 1 (N - K) ! = (N - K) * (N - K - 1) * (N - K - 2 ) * ... * 1 이때, N의 sub factorial과 K! 을 구해서 나누어주면 곱셈 횟수를 줄일 수 있다. ex) N = 5, K = 2 5 4 3 2 1 2 1 3 2 1 소스코드 소스코드 보기 출처 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net

풀이 두 좌표를 기준으로 반지름만큼의 원이 형성될 때 원의 둘레가 겹치는 좌표의 개수를 구하면 된다. 아래의 그림은 주어진 Test Case에 대한 시각화 자료이다. 만약 입력으로 주어지는 두 원이, 동일한 좌표와 반지름을 가진다면 '류재명'이 있을 수 있는 위치는 무한대이다. 두 원의 정보에 대한 입력을 struct Circle을 통해 입력받고, 두 원의 중심거리(d)와 두 원의 반지름의 차(diff_radius), 두 원의 반지름의 합(sum_radius)을 구해서 다음과 같은 비교를 통해 문제를 해결할 수 있다. 입력받은 두 원의 정보가 동일하다면 류재명이 있을 수 있는 위치는 무한대이다. d == sum_radius 이거나, d == diff_radius(아래 그림 참고)이면 한 접점에서만 만난다..