문제 정의 정수 n개가 담긴 배열 nums가 주어졌다고 가정해 봅시다. 이때 배열 안의 숫자들이 쌍별 서로소(pairwise coprime)인지, 집합별 서로소(setwise coprime)인지, 아니면 서로소가 아닌지 판별해야 합니다. 쌍별 서로소(pairwise coprime): 두 수 nums[i]와 nums[j]의 최대공약수가 gcd(nums[i], nums[j]) = 1일 때 이 두 수는 서로소입니다. 배열 내 모든 숫자 쌍(i < j)에 대해 이 조건이 성립해야 합니다. 집합별 서로소(setwise coprime

문제 이해하기 배열 nums에 n개의 숫자가 주어져 있다고 가정해 봅시다. 우리는 배열에서 두 숫자로 이루어진 쌍(pair)을 선택해야 하며, 다음 조건을 만족해야 합니다. 두 숫자의 배열 내 위치 차이 = 두 숫자의 합 n개의 원소를 가진 배열에서 만들 수 있는 전체 쌍의 개수는 n(n - 1)/2개입니다. 이 중에서 위 조건을 만족하는 쌍이 총 몇 개인지 구하는 것이 목표입니다. 예를 들어 입력이 n = 8, nums = {4, 2, 1, 0, 1, 2, 3, 3}이라면 출력은 13이 됩니다. 즉, 이 배열에는 조건을 만족하는

h × w 크기의 격자(grid)가 주어졌다고 가정해 보겠습니다. 격자를 구성하는 각 칸은 흰색과 검은색 두 가지 유형으로 나뉘며, 흰색 칸은 .으로, 검은색 칸은 #으로 표현됩니다. 격자 안에는 여러 개의 검은색 칸이 모여 하나의 다각형을 형성하고 있으며, 우리가 구해야 하는 값은 바로 이 다각형이 가지고 있는 변의 개수입니다. 단, 격자의 가장 바깥쪽 칸들은 항상 흰색이라는 조건이 주어집니다.예를 들어 h = 4, w = 4, grid = {...., .##., .##., ....}라는 입력이 주어진다면 출력은 4가 됩니다.검은

문제 개요가중치가 없는 무방향 그래프에 n개의 정점과 m개의 간선이 주어져 있다고 가정해 봅시다. 그래프에서 브리지(Bridge, 다리) 간선이란 해당 간선을 제거했을 때 그래프가 연결 상태를 잃고 분리되는 간선을 의미합니다. 이 글에서는 주어진 그래프에 포함된 브리지 간선의 개수를 구하는 프로그램을 작성해 보겠습니다. 단, 그래프에는 평행 간선(parallel edge)이나 자기 루프(self-loop)는 존재하지 않는다고 가정합니다.예를 들어 입력이 다음과 같다면,n = 5, m = 6, edges = {{1, 2}, {1, 3

문제 설명 h × w 크기의 격자가 주어졌다고 가정해 보겠습니다. 격자의 각 칸에는 전구 또는 장애물이 놓여 있을 수 있습니다. 전구가 있는 칸은 자기 자신과 상하좌우 네 방향의 칸들을 비추며, 빛은 장애물에 막히지 않는 한 계속 퍼져 나갑니다. 반면 장애물이 있는 칸은 조명될 수 없으며, 전구의 빛이 다른 칸까지 도달하는 것을 차단합니다. 따라서 전구의 좌표가 담긴 배열 bulb와 장애물의 좌표가 담긴 배열 obstacle이 주어졌을 때, 격자에서 조명되는 칸의 총 개수를 구해야 합니다. 입력 예시 예를 들어 h = 4, w =

문제 소개 h × w 크기의 격자가 주어졌다고 가정해 보겠습니다. 격자의 각 칸에는 전구 또는 장애물이 있을 수 있습니다. 전구가 놓인 칸은 왼쪽, 오른쪽, 위, 아래 네 방향의 칸을 밝히며, 빛은 장애물에 가로막히지 않는 한 계속 퍼져 나갑니다. 장애물이 있는 칸은 빛을 받을 수 없으며, 전구의 빛이 다른 칸에 도달하는 것을 차단합니다. 격자는 문자열 배열 형태로 주어지며, #은 장애물을, .은 빈 칸을 나타냅니다. 전구는 단 하나만 사용할 수 있고, 이를 가장 유리한 위치에 배치했을 때 비출 수 있는 칸의 최대 개수를 구하는 것

n개의 역이 m개의 선로로 연결되어 있다고 가정해 보겠습니다. 역에는 1부터 n까지 번호가 매겨져 있으며, 모든 선로는 양방향으로 통행할 수 있습니다. 우리의 목표는 src 역에서 dst 역까지 이동하는 것입니다.i번째 철도 노선의 양쪽 역 정보는 배열 roads에 담겨 있으며, 각 원소는 {station1, station2} 형식입니다. 또한 j번째 역에서는 그 역과 연결된 모든 역으로 향하는 기차가 kj 시간의 배수가 되는 시각마다 출발하고, 기차가 목적 역에 도착하는 데는 tj만큼의 시간이 걸립니다. 이 값들은 배열 depar

문제 설명두 개의 정수 n과 m이 주어지고, 네 개의 정수 {ai, bi, ci, di}로 이루어진 k개의 튜플이 있다고 가정해 봅시다. 배열 a, b, c, d가 주어지며, a[i]는 i번째 튜플의 a 값에 해당합니다.이제 n개의 양의 정수로 구성된 수열 dp를 생각해 보겠습니다. 이 수열은 다음 조건을 만족해야 합니다.1 <= dp[1] < dp[2] < ... < dp[n] <= m여기서 tally라는 지표를 정의합니다. tally는 dp[b[i]] − dp[a[i]] = c[i]를 만족하는 모든 인

중심 좌표가 (xc, yc)이고 높이가 h인 건물이 있다고 가정해 보겠습니다. 우리는 건물의 중심 좌표를 모르지만, x 좌표와 y 좌표 그리고 고도 값 a를 포함하는 n개의 정보를 제공받았습니다. 이때 좌표 (x, y)에서의 고도는 다음과 같이 정의됩니다.altitude = max(h - |x - xc| - |y - yc|, 0)즉, 주어진 정보들을 이용해 건물의 중심 좌표와 높이를 역으로 계산해야 합니다. 각 좌표 xi는 배열 x에, yi는 배열 y에, ai는 배열 a에 담겨 있습니다.예를 들어 입력이 n = 3, x = {3,

검은색 셀과 흰색 셀, 두 종류의 칸으로 이루어진 격자(grid)가 주어졌다고 가정해 봅시다. 검은색 셀은 #로, 흰색 셀은 .로 표현되며, 격자는 문자열 배열 형태로 입력됩니다. 우리가 수행해야 할 작업은 다음과 같습니다. 검은색 셀과 한 변을 맞대고 있는 흰색 셀을 모두 검은색으로 바꿉니다. 이 연산을 격자의 모든 셀이 검은색이 될 때까지 반복합니다. 격자 전체를 검은색으로 만드는 데 걸리는 반복 횟수를 계산합니다. 단, 처음 상태의 격자에는 반드시 검은색 셀이 하나 이상 존재해야 합니다. 예를 들어 입력이 h = 4, w

n개의 정점으로 이루어진 그래프가 주어져 있다고 가정해 보겠습니다. 정점은 1부터 n까지 번호가 매겨져 있으며, 배열 edges에 담긴 간선들로 서로 연결되어 있습니다. 또한 각 정점은 배열 values에 저장된 1부터 n 사이의 값을 하나씩 가지며, 이를 해당 정점의 x 값이라고 합니다.이제 그래프에서 슈퍼 꼭짓점(super vertex)을 찾아야 합니다. 정점 i는 다음 조건을 만족할 때 슈퍼 꼭짓점이라고 부릅니다.정점 1에서 정점 i까지의 최단 경로 위에, i번째 정점과 동일한 x 값을 가진 다른 정점이 존재하지 않아야 한다.

문제 소개2개의 행과 n개의 열로 이루어진 그리드가 주어졌다고 가정해 봅시다. 이 그리드는 서로 겹치지 않는 n개의 보드로 완전히 덮여 있으며, 각 보드는 빨강(red), 파랑(blue), 초록(green) 중 하나의 색으로 칠해야 합니다. 단, 서로 맞닿아 있는 두 보드는 같은 색으로 칠할 수 없고, 특별한 제약이 없다면 세 가지 색을 모두 사용할 필요도 없습니다.그리드의 배치는 배열 grid로 주어집니다. 같은 영문자로 표시된 칸들은 하나의 보드에 해당하고, 서로 다른 영문자는 서로 다른 보드를 의미합니다. 우리가 구해야 할 값

n개의 도시가 m개의 도로로 연결되어 있다고 가정해 봅시다. 도로는 모두 단방향으로, 출발지에서 목적지로만 이동할 수 있고 반대 방향으로는 갈 수 없습니다. 도로 정보는 {출발지, 목적지} 형식의 배열 roads로 주어집니다.각 도시에서는 밀이 서로 다른 가격에 거래됩니다. 배열 price의 i번째 값이 i번째 도시의 밀 가격을 나타냅니다. 여행자는 원하는 도시에서 밀을 사서, 도로가 허용하는 범위 내에서 다른 도시로 이동한 뒤 판매할 수 있습니다. 이때 여행자가 밀 거래를 통해 얻을 수 있는 최대 이익을 구하는 것이 문제의 목표입

크기가 h × w인 그리드가 주어졌다고 가정해 보겠습니다. 그리드의 모든 셀에는 특정한 값이 할당되어 있으며, 우리의 목표는 짝수 값을 가진 셀의 개수를 최대화하는 것입니다.이를 위해 다음과 같은 연산을 사용할 수 있습니다. 아직 선택하지 않은 셀 하나를 골라 해당 셀의 값을 1 감소시키고, 현재 셀과 세로 또는 가로로 인접한 다른 셀의 값을 1 증가시키는 방식입니다. 최종적으로 연산 횟수와 각 연산에 사용된 셀의 좌표를 출력해야 하며, 출력 형식은 다음과 같습니다.연산 횟수첫 번째 줄: (값이 감소된 셀 위치) - (값이 증가된

n개의 정점으로 구성되어 있고 최소한으로만 연결된(즉, 트리 형태의) 그래프가 주어졌다고 가정해 보겠습니다. 간선은 {출발점, 도착점, 가중치} 형식의 배열로 제공되며, 여기에 {출발점, 도착점} 형식의 쿼리가 q개 주어집니다. 각 쿼리마다 출발점에서 정점 k를 경유하여 도착점에 도달하는 최단 비용 경로를 찾고, 해당 경로의 비용을 출력해야 합니다.예를 들어 입력이 n = 6, q = 3, k = 1, edges = {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}}, queries

n개의 도시가 있고, 도시 사이를 연결하는 m개의 도로가 있다고 가정해 봅시다. 각 도로는 {출발지, 목적지, 가중치} 형식의 배열로 주어집니다. 여기서 s, t, k가 모두 도시를 나타내는 트리플릿(triplet) (s, t, k)를 정의합니다.우리가 해야 할 일은 도시 s에서 도시 t로 이동할 때 걸리는 최소 시간을 구하는 것입니다. 단, s에서 t로 이동하는 과정에서는 번호가 1부터 k 사이에 있는 도시만 경유할 수 있습니다. 만약 s에서 도시 t에 도달할 수 없다면 해당 경우는 0으로 처리합니다. 이렇게 모든 트리플릿 (s,

문제 개요 두 개의 배열 a와 b가 주어지며, 각각 n개와 m개의 값을 담고 있다고 가정해 보겠습니다. 우리는 두 배열의 값들을 활용해 n과 m 중 더 작은 값만큼의 쌍(pair)을 만들어야 합니다. 이때 각 쌍은 반드시 배열 a의 값 하나와 배열 b의 값 하나로 구성되어야 하며, 쌍을 이루는 두 값의 차이가 최소가 되도록, 가능한 한 모든 쌍에서 차이가 동일하게 맞추도록 짝을 지은 뒤 그 차이 값을 출력하는 것이 목표입니다. 예를 들어 입력이 다음과 같다고 해봅시다. n = 4, m = 4, a = {2, 3, 4, 7}, b =

문제 설명 한 회사에 총 n명의 직원이 있다고 가정해 보겠습니다. 모든 직원은 실력에 따라 등급을 부여받으며, 등급은 1부터 k까지의 번호로 매겨집니다. 등급 i를 가진 직원의 수는 배열 skill에 저장되며, skill[i]는 등급 i를 가진 직원 수를 나타냅니다. 이제 회사에 새로운 지점이 개설되어, 실력이 서로 다른 직원들을 해당 지점으로 전출해야 하는 상황입니다. 새 지점에 보내야 할 직원 수는 m명입니다. 다양한 실력을 가진 m명의 직원을 새 지점에 배치하려면, 다음 공식을 최소화하는 지점의 직원 등급 배분표 branch

h × w 크기의 행렬이 주어졌다고 가정해 보겠습니다. 행렬의 각 칸에는 영어 알파벳이 들어 있습니다. 우리가 만들어야 하는 것은 모든 행과 열이 회문(palindrome)인 새로운 행렬입니다. 즉, 어떤 방향에서 읽어도 앞뒤가 같은 형태가 되어야 합니다.단, 행렬을 구성할 때 다음 두 가지 제약 조건이 있습니다.주어진 행렬의 행과 열은 자유롭게 재배열할 수 있습니다.하지만 개별 원소는 절대 변경할 수 없습니다. 예를 들어 a를 b로 바꾸는 것은 허용되지 않습니다.이러한 조건 아래에서 회문 행렬을 만드는 것이 가능하면 true를,

문제 소개 세 개의 정수 N, M, K가 주어집니다. N개의 행과 M개의 열로 이루어진 격자의 모든 칸에 1 이상 K 이하의 정수를 하나씩 적는다고 가정해 봅시다. 이때 다음 조건을 만족하는 두 수열 A와 B를 정의합니다. 1부터 N까지의 각 i에 대해, A[i]는 i번째 행에 있는 모든 원소 중 최솟값입니다. 1부터 M까지의 각 j에 대해, B[j]는 j번째 열에 있는 모든 원소 중 최댓값입니다. 구해야 할 것은 가능한 쌍 (A, B)의 개수입니다. 답이 매우 커질 수 있으므로, 결과는 998244353으로 나눈 나머지를 반환