나무 막대로 정삼각형 만들기
문제 배경
나무 막대를 활용하여 정삼각형을 구성하는 방법에 대한 문제입니다.
문제 설명
n개의 나무 막대가 주어집니다. 이 중 4개의 막대를 선택하여 정삼각형을 만들 수 있는 경우의 수를 구하세요. 정답은 109+7로 나눈 나머지를 출력합니다.
입력 형식
첫 번째 줄에는 막대의 개수 n이 주어집니다. 두 번째 줄부터 n개의 줄에 걸쳐 각 막대의 길이 ai가 주어집니다 ...
7월 6일 00:09에 게시됨
2023년 7월 상하이 컴퓨터학회 경쟁 플랫폼 초급반 문제 풀이
T1 행 우선 탐색
문제 개요
n×m 크기의 격자가 다음 규칙으로 채워져 있습니다:
열 1열 2...열 m
행 112...m
행 2m+1m+2...2m
행 32m+12m+2...3m
...............
행 n.........nm
정수 c가 주어지면, c가 위치한 행과 열을 "행 열" 순서로 출력합니다.
핵심 아이디어
격자의 구조를 분석하면 두 가지 핵심 관계를 도출할 수 있습니다:
열 계산: c를 m으로 나눈 나머지 ...
6월 28일 00:15에 게시됨
조합론과 수론의 주요 개념들
조합론과 수론은 알고리즘 문제 해결에서 중요한 역할을 한다. 여기에서는 이 분야의 핵심적인 개념들과 이를 활용한 몇 가지 기법들을 다룬다.
조합론
가법 원리와 곱셈 원리
가법 원리에 따르면, 어떤 일을 수행하는 두 가지 방법이 있을 때 첫 번째 방법으로는 a개의 방법이 있고, 두 번째 방법으로는 b개의 방법이 있다면 총 a+b개의 방법으로 일을 완수할 수 있다. 곱 ...
6월 20일 17:51에 게시됨
전체 순열에서 K번째 수열 찾기
문제 설명
정수 수열 a₁, a₂, …, aₙ의 각 원소가 1부터 n 사이의 값을 가지며 중복이 없다면 이를 전체 순열(전체 배열)이라고 부릅니다. 예를 들어, [1,3,2]와 [4,3,2,1]은 모두 전체 순열입니다.
전체 순열들을 정렬할 때 다음과 같은 우선순위 규칙을 따릅니다:
길이가 n < m이면 a 수열이 앞섭니다.
길이가 n > m이면 b 수열이 앞섭니다.
길이가 같으면 사전순 ...
6월 3일 18:00에 게시됨
격자 동물 문제의 완전 탐색 풀이
문제 개요
격자 동물(Lattice Animals) 문제는 주어진 크기의 격자 내에서 특정한 연결된 블록 조합의 수를 세는 문제입니다. 이 문제는 복잡한 알고리즘 없이도 완전 탐색을 통해 해결할 수 있으며, 사전에 가능한 모든 경우를 계산하여 표 형태로 저장한 후 질의에 따라 바로 답을 출력하는 방식으로 구현됩니다.
접근 방법
해당 문제는 가능한 모든 연결된 블록의 형태 ...
6월 3일 00:41에 게시됨
[HAOI2008] 동전 구매 - 완전 배낭과 포함-배제 원리
문제 설명
4가지 종류의 동전이 있으며 각각의 액면가는 \(c_1, c_2, c_3, c_4\)입니다.
어떤 사람이 가게에서 물건을 \(n\)번 구매합니다. 각 구매마다 \(i\)번째 동전을 \(d_i\)개씩 가지고 있으며, 총 \(s\) 가치의 물건을 사려고 합니다. 각 구매에 대해 지불 방법의 수를 구하세요.
입력 형식
첫 번째 줄에는 다섯 개의 정수 \(c_1, c_2, c_3, c_4, n\)이 주어집니다. ...
6월 3일 00:38에 게시됨
NOIP 13연속 모의고사 #2 풀이
A번: 역순 배열직접 패턴을 분석해보면 규칙을 발견할 수 있다. 인덱스가 홀수번째끼리, 짝수번째끼리 서로 인접하며, 전체 배열은 홀수/짝수 인덱스 그룹이 번아 등장하는 형태가 된다.구체적으로 다음과 같이 구성된다:n이 홀수: aₙ, aₙ₋₂, ... , a₁ 뒤에 a₂, a₄, ... , aₙ₋₁n이 짝수: aₙ, aₙ₋₂, ... , a₂ 뒤에 a₁, a₃, ... , aₙ₋₁시간 복잡도는 O(n)이다.#include <b ...
5월 28일 16:51에 게시됨
COTS 2025 문제 풀이 및 코드 모음
개요
COTS 2025 대회에서 출제된 6개 문제(A~F)의 풀이와 구현 코드를 정리합니다. 각 문제는 서로 다른 알고리즘 기법을 요구하며, 복잡도와 구현 세부사항에 중점을 둡니다.
[COTS 2025] A - 상 배분 / Hijerarhija
트리 DP와 배낭 문제를 결합한 문제입니다. 각 노드에서 자식 노드들의 상태를 합치며 최적해를 구합니다.
const int MAXN = 5e3 + 5;
const int INF = 1 ...
5월 22일 14:15에 게시됨