2025-11-05 NOIP 모의 대회 2 후기
결론 짧게:
100+0+0+0 점수.
T1: 소 Z의 장갑
문제 설명
길이가 \(n\)인 배열 \(a\)와 길이가 \(m\)인 배열 \(b\)가 주어집니다.
이 배열에서 \(\min(n,m)\)개의 쌍 \(a_i, b_j\)를 매칭해야 합니다. 각 숫자는 한 번만 매칭할 수 있습니다.
매칭의 비용은 \(|a_i - b_j|\)이며, 매칭 그룹의 비용은 이들 중 최댓값입니다. 이 최댓값을 최소화해야 합니다.
대회 당시
탐욕 ...
7월 31일 09:43에 게시됨
NOIP2018 Day2T2 填数游戏
이 문제는 n×m 격자에 0과 1을 채워넣는 방식의 수를 세는 조합 문제입니다. 핵심 조건은 오른쪽 우선 경로의 01 문자열이 아래쪽 우선 경로의 01 문자열보다 사전순으로 작거나 같아야 한다는 것입니다.
작은 케이스 분석과 패턴 발견
먼저 n ≤ 3인 경우를 완전탐색으로 해결할 수 있습니다. DFS를 통해 모든 가능한 배치를 검증하면 다음과 같은 결과를 얻습니다:
2 : ...
7월 23일 22:03에 게시됨
NOIP 연습 세션 #1 상세 문제 풀이
문제 A: 점 쌍의 각도 최적화
이 문제는 두 점 사이의 관계를 최적화하는 전형적인 그리디 알고리즘 문제입니다. 데이터 범위를 고려했을 때 $O(n \log n)$ 시간 복잡도가 필요하며, 정렬을 활용해야 합니다.
핵심 아이디어는 좌표축을 45도 회전시키는 것입니다. 기존 좌표 $(x, y)$를 $(x+y, x-y)$로 변환하면, $y=x$ 또는 $y=-x$에 가장 가까운 값을 찾는 문제가 됩니 ...
6월 28일 01:33에 게시됨
:NOIP 시뮬레이션 경진대회 문제 풀이
T1 다채로운 색상
문제는 다음과 같습니다:
nxm 크기의 행렬이 주어집니다.
(i,j) 위치에는 색깔 ci,j가 있습니다.
네 모서리의 색상이 모두 동일하지 않은 모든 하위 행렬의 수를 구하세요.
시간 복잡도 O(n²m)으로 해결할 수 있습니다. 두 행을 선택한 뒤 열을 스캔하면서 해당 열의 값들이 같으면 답에 기여할 가능성이 있습니다. 이를 위해 카운트 배열을 ...
6월 17일 19:19에 게시됨
NOIP 2012 차량 여행 문제 해결: 양방향 연결 리스트와 이진 리프팅 최적화
문제 개요
NOIP 2012 심화 그룹의 '차량 여행' 문제는 두 운전자 A와 B가 번갈아 가며 동쪽(도시 번호가 증가하는 방향)으로 이동할 때의 경로를 시뮬레이션하고 최적의 출발지를 찾는 문제입니다.
운전 규칙: A가 먼저 운전하고 B가 다음에 운전하는 방식으로 번갈아 진행합니다.
도시 선택 기준:
운전자 B: 현재 도시와 해발 고도 차이의 절댓값이 가장 작은 도 ...
6월 8일 01:37에 게시됨
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에 게시됨