문제 설명두 값 p와 q가 주어졌다고 가정해 보겠습니다. 점들이 균일한 간격으로 배치된 p행 × q열 그리드에서 만들 수 있는 고유한 정사각형의 개수를 구하는 것이 목표입니다. 답이 매우 커질 수 있으므로, 최종 결과는 10⁹ + 7로 나눈 나머지(mod)를 반환해야 합니다.여기서 말하는 정사각형은 네 개의 점이 정사각형의 네 꼭짓점을 이루는 경우를 의미합니다. 네 변의 길이는 모두 같아야 하며, 반드시 그리드의 축과 평행할 필요는 없습니다. 즉, 축에 정렬된 사각형뿐만 아니라 기울어진 사각형도 모두 포함됩니다.예를 들어 입력이 p

소문자로만 이루어진 문자열 i와 하나의 정수 j가 주어졌다고 가정해 봅시다. 이때 다음 세 가지 조건을 모두 만족하는 문자열이 총 몇 개인지 구해야 합니다.문자열 i와 길이가 같아야 합니다.사전순(lexicographically)으로 i보다 작거나 같아야 합니다.같은 문자가 연속으로 나오는 횟수가 j를 초과하지 않아야 합니다.정답은 결과를 10^9 + 7로 나눈 나머지(modulo) 형태로 계산해야 합니다.예를 들어 입력이 i = app, j = 2라면 출력은 405가 됩니다.해결 접근 방법이 문제는 각 자리마다 가능한 문자를 하나

문제 개요0부터 N-1까지 번호가 붙은 N개의 아이템이 있다고 가정해 보겠습니다. 크기가 S인 2차원 리스트 sets가 주어지며, i번째 세트는 sets[i][2]의 가격에 구매할 수 있고, 구매 시 sets[i][0]부터 sets[i][1] 범위에 속한 모든 아이템을 한꺼번에 얻게 됩니다. 또한 크기가 N인 리스트 removals가 주어져서, removals[i]만큼의 비용을 지불하면 i번째 아이템 하나를 버릴 수 있습니다.목표는 0부터 N-1까지의 모든 아이템을 정확히 하나씩 확보하는 최소 비용을 구하는 것이며, 만약 불가능하다

문제 개요여러 문제가 출제되지만, 단 하나의 문제를 해결하는 순간 대회가 종료되는 프로그래밍 대회를 생각해 봅시다. 길이가 같은 두 개의 리스트 points와 chances가 주어지며, i번째 문제는 chances[i]%의 확률로 풀어서 points[i]점을 획득할 수 있습니다. 또한 시도할 수 있는 문제의 최대 개수를 나타내는 값 k가 주어지고, 동일한 문제는 두 번 시도할 수 없습니다.최적의 전략을 세웠을 때 대회에서 얻을 수 있는 점수의 기댓값을 구하고, 그 값을 가장 가까운 정수로 반올림하는 것이 목표입니다. i번째 문제를

문제 개요x+y=z 형태의 방정식을 나타내는 문자열 s가 주어졌다고 가정해 보겠습니다. 이 문제의 목표는 방정식이 실제로 성립하도록 만들기 위해 문자열에 삽입해야 하는 숫자(자릿수)의 최소 개수를 구하는 것입니다.예를 들어 입력이 s = 2+6=7이라면 출력은 2가 됩니다. 1과 2를 각각 삽입하여 방정식을 21+6=27로 바꾸면 등식이 성립하므로, 필요한 수정 횟수는 총 2회입니다.해결 접근 방법이 문제는 세 수 A, B, C의 각 자릿수를 뒤에서부터 한 자리씩 비교하면서 자리올림(carry)을 함께 추적하는 재귀적 동적 계획법(

문제 개요2차원 정수 리스트 edges가 하나의 무방향 그래프(undirected graph)를 나타낸다고 가정해 보겠습니다. 입력의 각 행은 [u, v, w] 형태의 간선 정보를 담고 있으며, 이는 노드 u와 v가 서로 연결되어 있고 해당 간선의 가중치가 w임을 의미합니다. 그래프는 0부터 n-1까지 총 n개의 노드로 구성됩니다.여기서 경로의 비용은 다음과 같이 정의됩니다.경로 비용 = (경로에 포함된 간선의 개수) × (경로상 간선 가중치의 최댓값)우리가 구해야 할 것은 노드 0에서 출발하여 노드 n-1에 도달하는 경로 중 최소

리스트의 파워(power)는 모든 인덱스에 대해 (인덱스 + 1) × 해당 위치의 값을 곱한 뒤 모두 더한 합으로 정의됩니다. 수식으로 나타내면 다음과 같습니다.$$\displaystyle\sum\limits_{i=0}^{n-1} (i+1)\times list[i]$$문제 설명N개의 양의 정수로 이루어진 리스트 nums가 주어졌다고 가정해 보겠습니다. 우리는 리스트에서 임의의 값을 하나 선택해 교환(swap)이 아닌 이동(move) 방식으로 원하는 위치, 즉 리스트의 맨 앞이나 맨 끝을 포함한 어느 곳으로든 옮길 수 있습니다. 물론

문제 소개숫자 k가 주어졌을 때, 1부터 k까지의 모든 값으로 나누어 떨어지는 가장 작은 양의 정수 x를 생각해 보겠습니다. 다시 말해, x가 1부터 k까지의 모든 숫자로 균등하게 나누어질 때의 최솟값을 찾는 것입니다. 우리의 목표는 이 x의 끝에 연속해서 붙어 있는 0(후미 0, trailing zero)의 개수를 구하는 것입니다.예시입력이 k = 6이라고 가정해 보겠습니다. 이때 조건을 만족하는 가장 작은 x는 60입니다. 60은 1, 2, 3, 4, 5, 6 모두로 나누어 떨어집니다. 그리고 60의 끝에는 0이 하나만 붙어 있

숫자로 이루어진 리스트 nums가 있다고 가정해 보겠습니다. 여기서 허용되는 연산은 인접한 두 값을 골라 그 합으로 하나의 값으로 병합하는 것입니다. 이때 리스트 전체가 비증가(non-increasing) 상태, 즉 왼쪽에서 오른쪽으로 갈수록 값이 커지지 않는 형태가 되도록 만들어야 하며, 필요한 최소 연산 횟수를 구하는 것이 이 문제의 목표입니다. 예를 들어 입력이 nums = [2, 6, 4, 10, 2]라고 해 보겠습니다. 먼저 [2, 6]을 합쳐 [8, 4, 10, 2]를 만들고, 이어서 [8, 4]를 합쳐 [12, 10,

문제 설명소문자로만 구성된 문자열 s가 주어졌을 때, s의 모든 부분 문자열에 대해 각 부분 문자열 안에서 한 번만 등장하는(고유한) 문자의 개수를 모두 더한 값을 구해야 합니다. 결과가 매우 커질 수 있으므로 10⁹+7로 나눈 나머지를 반환합니다.예를 들어 s = xxy라면 정답은 6입니다. 각 부분 문자열과 그 기여도는 다음과 같습니다.x : 1x : 1y : 1xx : 0 — x가 두 번 등장하므로 고유하지 않음xy : 2xxy : 1 — x는 고유하지 않고 y만 계산됨전체 합계는 1 + 1 + 1 + 0 + 2 + 1 = 6

0은 빈 셀을, 1은 벽을 나타내는 2차원 이진 행렬이 주어졌다고 가정해 보겠습니다. 이때 왼쪽 상단 셀과 오른쪽 하단 셀 사이에 어떤 경로도 존재하지 않도록 만들기 위해 벽으로 바꿔야 하는 셀의 최소 개수를 구해야 합니다. 단, 왼쪽 상단 셀과 오른쪽 하단 셀에는 벽을 설치할 수 없으며, 이동은 상·하·좌·우 방향으로만 가능하고 대각선 이동은 허용되지 않습니다.예를 들어 입력이 다음과 같다고 해보겠습니다.0000010001100000이 경우 출력값은 2이며, 벽을 배치한 결과는 다음과 같습니다.0100010001100010문제 해

다음과 같이 여러 값으로 구성된 2차원 행렬이 있다고 가정해 보겠습니다.0: 빈 셀1: 사람2: 불3: 벽행렬에는 사람이 한 명만 있으며, 매 턴마다 불이 상하좌우 네 방향으로 확산됩니다. 단, 불은 벽을 통과하지 못합니다. 우리가 확인해야 할 것은 사람이 행렬의 왼쪽 위 모서리 또는 오른쪽 아래 모서리에 도달할 수 있는지 여부입니다.여기서 중요한 규칙이 있습니다. 매 턴에 사람이 먼저 이동한 후 불이 확산됩니다. 따라서 사람이 어떤 셀에 도착하는 것과 같은 턴에 불이 해당 셀로 번져오더라도, 사람은 이미 그 셀에 먼저 도착한 것이

문제 개요소문자 x와 y로만 구성된 문자열 s가 주어졌다고 가정해 보겠습니다. 한 번의 연산으로 문자 하나를 골라 x를 y로 바꾸거나, 반대로 y를 x로 바꿀 수 있습니다. 이때 문자열 안의 모든 x가 모든 y보다 앞쪽에 오도록 만들기 위해 필요한 최소 연산 횟수를 구하는 것이 목표입니다.예를 들어 입력이 s = yxyyyyxyxx라면, 출력은 4가 됩니다.접근 방법핵심 아이디어는 문자열을 왼쪽에서 오른쪽으로 한 번만 훑으면서, 각 위치를 분할 지점으로 삼는 것입니다. 어떤 지점을 기준으로 할 때 비용은 다음과 같이 정의됩니다.y_

문제 소개두 개의 문자열 s, t와 또 다른 문자열 r이 주어져 있다고 가정해 보겠습니다. 이 문제의 목표는 s와 t에 담긴 문자들을 원래 순서를 유지한 채 교차로 배치(인터리빙)했을 때 r을 만들어낼 수 있는지 확인하는 것입니다.예를 들어 입력이 s = xyz, t = mno, r = xymnoz라면 결과는 True입니다. xymnoz는 xyz와 mno의 문자를 차례대로 섞어서 만들 수 있기 때문입니다.해결 접근 방식이 문제는 재귀 호출을 이용하면 자연스럽게 해결할 수 있습니다. 핵심 아이디어는 매 단계마다 r의 첫 글자가 s의

숫자 리스트 nums가 주어졌을 때, 인접한 모든 값의 쌍의 합이 완전제곱수(perfect square)가 되도록 만드는 순열의 개수를 구하는 문제입니다. 두 순열 A와 B는 임의의 인덱스 i에서 A[i]와 B[i]가 서로 다른 경우가 하나라도 존재하면 서로 다른 순열로 간주합니다. 예를 들어 입력이 nums = [2, 9, 7]이라면 출력은 2입니다. 조건을 만족하는 순열이 [2, 7, 9]와 [9, 7, 2], 이렇게 두 가지이기 때문입니다. 알고리즘 설계 이 문제는 백트래킹(backtracking) 기법으로 효율적으로 해결할

문제 개요candies라는 숫자 리스트가 주어지고, 두 명의 플레이어가 누가 더 많은 사탕을 모으는지 겨루는 게임이 있다고 가정해 보겠습니다. 이 게임은 턴제로 진행되며, 1번 플레이어가 먼저 시작합니다. 각 턴마다 플레이어는 리스트의 맨 앞 또는 맨 뒤에 있는 사탕 중 하나를 가져갈 수 있습니다. 우리가 확인해야 할 것은 1번 플레이어가 최적의 전략을 사용했을 때 상대방보다 더 많은 사탕을 모을 수 있는지 여부입니다.예를 들어 입력이 candies = [1, 4, 3, 8]이라면 결과는 True가 됩니다. 1번 플레이어가 첫 턴에

두 명의 플레이어가 게임을 진행한다고 가정해 보겠습니다. 여러 개의 캔디가 한 줄로 놓여 있고, 1번 플레이어에게는 각 캔디의 점수 값을 나타내는 숫자 리스트 nums가 주어집니다. 각 플레이어는 자신의 차례에 줄 맨 앞에서 캔디를 1개, 2개 또는 3개 선택하여 리스트에서 제거하고, 해당 캔디들의 점수 합계를 자신의 점수에 더합니다. 모든 캔디가 제거되면 게임이 종료되며, 더 높은 점수를 가진 플레이어가 최종 승자가 됩니다. 우리가 확인해야 할 것은 1번 플레이어가 이 게임에서 승리할 수 있는지 여부입니다.예를 들어 입력이 num

문제 설명2차원 행렬이 주어지고, 각 셀 matrix[r][c]에는 해당 위치에 놓인 동전의 개수가 저장되어 있다고 가정해 봅시다. 우리는 행렬의 아무 위치에서나 출발하여 상하좌우 네 방향으로만 이동하면서(대각선 이동은 불가) 동전을 최대한 많이 모으려고 합니다.단, 다음 규칙이 적용됩니다.어떤 셀에 도착하면 그 셀의 동전을 모두 수집하고, 해당 셀의 값은 0이 됩니다.동전이 0개인 셀은 방문할 수 없습니다.목표는 수집할 수 있는 동전의 최대 개수를 구하는 것입니다.예시입력 행렬이 다음과 같다면,2433602012출력은 18이 됩니

문제 소개세 가지 값 중 하나를 가지는 2차원 행렬(격자)이 주어졌다고 가정해 보겠습니다.0 : 빈 셀1 : 동전이 있는 셀-1 : 벽(지나갈 수 없는 셀)왼쪽 상단 셀에서 출발해 오른쪽 또는 아래 방향으로만 이동하여 오른쪽 하단 셀에 도달한 뒤, 다시 위쪽 또는 왼쪽 방향으로만 이동하여 시작 지점으로 돌아와야 합니다. 이때 동전을 주우면 해당 셀의 값은 0으로 바뀌므로, 같은 동전을 두 번 모을 수 없습니다. 만약 오른쪽 하단 셀에 도달할 수 없다면 0을 반환해야 합니다.예시 입력011111-111011이 경우 출력값은 8입니다.

숫자로만 이루어진 문자열 s와 정수 k가 주어졌을 때, 문자열 s를 [1, k] 범위에 속하는 숫자들의 목록으로 나눌 수 있는 서로 다른 방법의 개수를 구하는 문제입니다. 답이 매우 커질 수 있으므로 결과는 10^9 + 7로 나눈 나머지를 반환합니다.문제 예시예를 들어 s = 3456, k = 500이 입력으로 주어지면 출력은 7이 됩니다. 다음과 같은 7가지 방법으로 문자열을 분할할 수 있기 때문입니다.[3, 4, 5, 6][34, 5, 6][3, 4, 56][3, 45, 6][34, 56][345, 6][3, 456]풀이 접근