문제 개요하나의 숫자 n이 주어졌을 때, 이를 합이 n이 되도록 양의 정수들의 내림차순(비증가) 수열로 분할할 수 있습니다. 이때 분할의 가중치(weight)란 분할을 이루는 요소 중 첫 번째 요소와 값이 같은 요소의 개수를 의미합니다.몇 가지 예를 들어 보겠습니다.분할 [1,1,1,1,1]의 가중치는 5입니다.분할 [5,5,3,3,3]의 가중치는 2입니다.분할 [9]의 가중치는 1입니다.우리가 구해야 할 것은 숫자 n의 모든 분할에서 나타날 수 있는 서로 다른 가중치의 개수입니다.예시입력이 n = 7이라면 출력은 4가 됩니다. 서

문제 설명 n개의 문자로 이루어진 문자열 S가 있다고 가정해 보겠습니다. S는 영어 대소문자로만 구성된 단어들이 공백 하나로 구분되어 있는 형태입니다. 여기서 단어의 볼륨(volume)은 해당 단어에 포함된 대문자의 개수를 의미하며, 텍스트 전체의 볼륨은 모든 단어 중에서 가장 큰 볼륨 값입니다. 즉, 우리가 구해야 할 답은 주어진 텍스트의 볼륨입니다. 예를 들어 Paper MILL이라는 문장을 보면, Paper의 볼륨은 1(P), MILL의 볼륨은 4(M, I, L, L)이므로 텍스트 전체의 볼륨은 4가 됩니다. 풀이 접근 방

3×3 크기의 행렬이 있고, 각 칸에는 X 또는 . 문자가 들어 있다고 가정해 봅시다. 이때 이 패턴이 중심 대칭(center symmetry)을 이루는지 아닌지를 확인하는 프로그램을 작성해야 합니다. 중심 대칭이란 행렬의 중앙 지점을 기준으로 180도 회전했을 때 원래 모양과 완전히 같은 형태가 되는 대칭 구조를 의미합니다.예를 들어 입력이 다음과 같다면,XX.....XX중앙을 기준으로 대각선 방향의 요소들이 서로 같으므로 출력 결과는 True가 됩니다.풀이 접근 방법3×3 행렬에서 중심 대칭 여부는 중앙 칸(1, 1)을 기준으로

크기가 n인 배열 A와 하나의 숫자 d가 주어졌다고 가정해 봅시다. 드림랜드(Dreamland) 군대의 규정에 따르면, 정찰 부대는 반드시 두 명의 병사로 구성되어야 합니다. 또한 두 병사의 신체 조건이 크게 차이 나지 않아야 하므로, 두 병사의 키 차이는 최대 d센티미터를 넘을 수 없습니다.병사 n명의 키가 배열 A에 저장되어 있으며, 그중에는 키가 같은 병사도 있습니다. 우리가 구해야 할 것은 이 n명의 병사 중에서 정찰 부대를 편성할 수 있는 경우의 수입니다.예를 들어 입력이 A = [10, 20, 50, 60, 65], d

문제 정의 숫자 p와 n개의 원소를 가진 배열 X가 있다고 가정해 봅시다. 버킷이 p개인 해시 테이블이 있으며, 각 버킷은 0부터 p-1까지 번호가 매겨집니다. 우리는 배열 X에 있는 n개의 숫자를 이 해시 테이블에 삽입하려고 합니다. X[i]가 들어갈 버킷은 해시 함수 h(X[i])에 의해 결정되며, 여기서 h(k) = k mod p입니다. 하나의 버킷에는 두 개 이상의 원소를 저장할 수 없습니다. 따라서 이미 차 있는 버킷에 새로운 숫자를 삽입하려고 하면 충돌(collision)이 발생했다고 합니다. 이 문제에서는 충돌이 발생

문제 개요 n개의 요소를 가진 배열 A와 하나의 숫자 s가 주어진 상황을 가정해 보겠습니다. 탁자 위에는 텅 빈 물컵 하나와 물이 담긴 물컵 n개가 놓여 있으며, 이 게임에는 여러 명의 플레이어가 참여합니다. 각 턴마다 플레이어는 물이 든 컵 하나를 골라 그 안의 물을 전부 빈 컵에 부어야 하고, 물이 넘쳐흐르면 해당 플레이어는 패배합니다. 따라서 우리가 확인해야 할 것은 모든 플레이어가 승자가 될 수 있는지, 즉 컵이 넘치지 않는지 여부입니다. 단, 컵이 이미 가득 차 있다면 다음 플레이어는 자신의 턴을 진행하지 않습니다. 여기서

문제 소개 n × n 크기의 행렬이 하나 주어집니다. 이 행렬 속 1이 아닌 모든 숫자가 자신과 같은 행에 있는 어떤 수와 같은 열에 있는 어떤 수의 합으로 표현될 수 있을 때, 그 행렬을 좋은(good) 행렬이라고 부릅니다. 이 글에서는 주어진 행렬이 좋은 행렬인지 여부를 판별하는 C++ 코드를 살펴보겠습니다. 예를 들어 입력이 다음과 같다고 가정해 보겠습니다. 112231641 이 경우 출력은 True입니다. 왼쪽 아래 모서리의 6은 바로 위에 있는 2와 오른쪽에 있는 4의 합(2 + 4 = 6)이므로 조건을 충족하기 때문입니다

두 개의 정수 n과 h, 그리고 m개의 삼중항(triplet)으로 이루어진 배열 T가 주어집니다. 여기서 T[i] = (li, ri, xi) 형태입니다. 도로변에는 집을 지을 수 있는 자리가 총 n곳 있으며, 각 자리는 1부터 n까지 번호가 매겨져 있습니다. 집의 높이는 0부터 h 사이의 값으로 지을 수 있고, 어떤 자리에 높이 k인 집을 지으면 k2만큼의 수익을 얻게 됩니다. 여기에 m개의 구역 제한 조건이 붙습니다. i번째 제한은 “li번째 자리부터 ri번째 자리까지 구간에서 가장 높은 집의 높이는 xi를 넘을 수 없다”는 의미

문제 소개 n개의 요소로 이루어진 배열 A가 있고, 각 요소의 값은 -1 또는 1입니다. 여기에 m개의 구간 쿼리 Q가 주어지며, 각 쿼리는 Q[i] = (li, ri) 형태입니다. 배열 A의 요소들을 자유롭게 재배열할 수 있을 때, li번째부터 ri번째까지 구간의 합을 정확히 0으로 만들 수 있다면 해당 쿼리의 답은 1, 만들 수 없다면 0입니다. 목표는 모든 쿼리에 대한 답을 효율적으로 구하는 것입니다. 예를 들어 입력이 A = [-1, 1, 1, 1, -1], Q = [[1, 1], [2, 3], [3, 5], [2, 5],

두 개의 숫자 m(월)과 d(그 달 1일의 요일)가 주어졌다고 가정해 봅시다. 달력에서 요일은 열(column)로 표현되고, 날짜는 행(row)으로 표현됩니다. 우리가 구하고자 하는 것은 주어진 월 m과 그 달 첫날의 요일 d가 있을 때, 해당 달력을 완성하는 데 몇 개의 열이 필요한지입니다. (단, 윤년은 고려하지 않습니다.)예를 들어 입력이 m = 11, d = 6이라면 출력은 5가 됩니다. 11월 1일이 토요일이고, 11월은 총 30일이므로 5개의 열이면 충분하기 때문입니다.해결 접근 방법이 문제는 다음 두 단계만으로 간단히

문제 설명n개의 서로 다른 원소로 이루어진 배열 A가 있다고 가정해 봅시다. 어떤 회사의 현장(onsite) 결승전에 참가할 수 있는 파이널리스트들이 있으며, 이들의 예선 순위가 배열 A에 담겨 있습니다. 우리가 구해야 할 것은 현장 결승 참가 초대를 거절한 참가자의 최소 인원입니다. 현장 결승의 정원은 총 25명이며, 이 중 일부는 초대를 수락하고 일부는 거절했다고 볼 수 있습니다.예를 들어 입력이 다음과 같다고 해보겠습니다.A = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18

문제 설명n개의 요소로 이루어진 배열 A와 두 개의 정수 k, x가 주어졌다고 가정해 보겠습니다. i번째 작업을 완료하는 데는 A[i]만큼의 시간이 걸리며, 배열 A는 비내림차순으로 정렬되어 있습니다.Amal은 최대 k개의 작업을 골라 해당 작업들을 원래 소요 시간인 A[i] 대신 x 단위의 시간으로 처리할 수 있습니다. 단, x는 모든 A[i] 중 최솟값보다 작아야 합니다. 우리의 목표는 Amal이 모든 작업을 완료하는 데 필요한 최소 시간을 구하는 것이며, Amal은 동시에 두 개 이상의 작업을 수행할 수 없습니다.예를 들어 입

숫자 n이 주어져 있다고 가정해 보겠습니다. 여러 명의 어린이가 원형으로 서 있으며, 시계 방향 순서대로 1부터 n까지 번호가 붙어 있고, 1번 어린이가 공을 들고 있습니다. 먼저 1번 어린이가 시계 방향으로 바로 옆 어린이(2번)에게 공을 던집니다. 그다음 2번 어린이는 한 명을 건너뛴 4번 어린이에게, 이어서 4번 어린이는 7번 어린이에게 공을 던지는 식으로 게임이 진행됩니다. 즉, 던질 때마다 이동 거리가 한 칸씩 늘어납니다. 공을 던질 때는 원의 시작점을 넘어 돌아갈 수도 있으며, 이렇게 진행하면 모든 어린이가 공을 받는

문제 설명 크기가 n인 두 배열 P와 T, 그리고 정수 c가 주어집니다. Amal과 Bimal은 n개의 문제로 구성된 수학 경시 대회에 참가합니다. i번째 문제의 초기 배점은 P[i]이고, 푸는 데 걸리는 시간은 T[i]입니다. 두 배열은 모두 오름차순으로 정렬되어 있으며, c는 분당 감점 계수입니다. 대회 시작 후 x분째에 문제를 제출하면 해당 문제에서 max(0, P[i] − c × x)점을 받게 됩니다. Amal은 문제를 1번부터 n번까지 순서대로 풀고, Bimal은 n번부터 1번까지 역순으로 풉니다. 우리가 할 일은 누가

문제 설명세 개의 숫자 k, l, m과 n개의 원소를 가진 배열 A가 주어졌다고 가정해 보겠습니다. 한 강도가 은행 강도 시도에는 실패했지만, 은행의 모든 금고를 여는 데는 성공했습니다. 이 실패한 강도 사건을 틈타 어떤 사람이 금고에서 돈을 훔치려 합니다.금고들은 일렬로 늘어서 있으며, 모든 금고에는 총 n장의 지폐가 남아 있습니다. i번째 지폐는 A[i]번 금고에 들어 있습니다. 현재 은행 직원은 k번 금고에 있으며, 경비원 두 명이 배치되어 있습니다. 한 명은 l(k보다 작음)번 금고를 지키고 있어 왼쪽에 위치하고, 다른 한

문제 개요n × n 크기의 정사각형 보드가 있다고 가정해 봅시다. 아말(Amal)과 비말(Bimal)은 게임을 진행하면서 나름의 규칙에 따라 보드의 각 칸에 숫자를 적어 나갑니다. 현재 보드에는 게임이 종료된 후의 숫자들이 남아 있습니다. 누가 승리했는지 판단하려면 승리 칸(winning square)의 개수를 계산해야 합니다.특정 칸이 승리 칸인지 판단하는 방법은 다음과 같습니다.해당 칸과 같은 열(column)에 있는 모든 숫자의 합을 구합니다.같은 방식으로 해당 칸과 같은 행(row)에 있는 모든 숫자의 합을 구합니다.열의 합

두 개의 숫자 n과 k가 주어졌다고 가정해 봅시다. 콘테스트에는 총 n명의 학생이 참가하며, 이들 중 일부는 기념품을 받고, 일부는 상장을 받으며, 나머지는 아무것도 받지 못합니다. 무언가를 받은 참가자를 승자라고 부릅니다.다만 기념품과 상장의 수를 정하는 데는 몇 가지 규칙이 있습니다.상장의 수는 반드시 기념품 수의 정확히 k배여야 합니다.승자의 총 수는 n/2를 초과할 수 없습니다.승자가 한 명도 없어도 괜찮습니다.이러한 규칙에 따라 가능한 최대 승자 수를 구한 뒤, 그때 기념품을 받은 학생 수, 상장을 받은 학생 수, 그리고

C++ switch 문이란? 조건문은 프로그램의 흐름을 제어하고 특정 코드 블록이 언제 실행될지 지정하는, 모든 프로그래밍 언어에 공통으로 등장하는 핵심 요소입니다. C++에서 가장 널리 쓰이는 조건문은 if 문과 if … else 문입니다. 여기에 더해 C++은 switch 문도 제공합니다. switch 문은 하나의 표현식을 여러 후보 case와 비교하여, 일치하는 case가 있으면 해당 코드 블록을 실행합니다. 동작 방식을 보면 수많은 if … else 문이 이어진 if 문과 유사하다고 할 수 있습니다. 이 글에서는 예제와

C++ 열거형(enum)이란? 열거형(enumerated type)은 사용자가 직접 정의하는 데이터 타입으로, 미리 정해 놓은 값의 집합 중 하나만 가질 수 있습니다. 프로그래밍에서 열거형은 변수가 특정 값 집합 중 하나만 저장하도록 제한하고 싶을 때 자주 사용됩니다. 예를 들어, 변수에 요일 값만 저장되기를 원한다면 열거형을 활용하는 것이 좋은 선택입니다. 이 글에서는 예제와 함께 C++ 열거형의 기본 개념, 열거형을 정의하는 방법, 그리고 코드에서 열거형을 사용하는 방법까지 차근차근 살펴봅니다. 끝까지 읽고 나면 C++에서

if...else는 C++에서 사용되는 조건문입니다. C++의 if 문은 주어진 조건이 참일 때 특정 코드 블록을 실행하고, if...else 문은 동일한 방식으로 작동하지만 조건이 거짓일 경우 두 번째 코드 블록을 실행한다는 점이 다릅니다. 또한 if와 if...else 문은 중첩해서 사용할 수도 있습니다. 조건문은 모든 프로그래밍 언어에서 빼놓을 수 없는 핵심 요소입니다. 조건문을 사용하면 프로그램 내에서 특정 조건이 충족되는지에 따라 코드를 실행할지 여부를 결정할 수 있습니다. C++에서 if와 if...else 문은