MX-S 모의고사 풀이 노트
T1: 메시지 필터링
문제 개요
총 n개의 채팅방을 순서대로 확인하며, 각 메시지에 bie 부분 문자열이 포함되어 있고 아직 전송한 적 없는 경우에만 전송한다. 전송할 메시지가 없는 채팅방은 특정 문구를 출력한다.
해결 방법
문자열 탐색과 중복 체크가 핵심이다. bie 존재 여부는 단순 순회로 확인하고, 중복 방지를 위해 해싱 기법을 활용한다. 더블 해싱을 적용해 충돌 ...
7월 26일 03:02에 게시됨
NOIP 모의 대회 8 회고: 조합 계산과 동적 계획법 기반 문제 풀이
T1: 좋은 수 판별하기
문제는 길이 n의 정수 배열 a가 주어졌을 때, 각 원소 a[i]가 "좋은 수"인지 판단하는 것이다. 여기서 "좋은 수"란, 인덱스가 i보다 작은 세 개의 원소 a[j], a[k], a[l]의 합이 a[i]와 일치하는 경우를 말한다. 단, 같은 인덱스는 중복 사용할 수 없다.
제한 조건이 n ≤ 5000이므로, 최악의 경우 O(n²) 정도의 시간 복잡도를 허용할 수 있다. 따라서 ...
6월 28일 19:49에 게시됨