14699번: 관악산 등산 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미 www.acmicpc.net Dynamic Programming 높은 위치부터 계산 제목 관악산 등산 조건 시간 제한 : 1 초 메모리 제한 : 512 MB 문제 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미래를 보고 답해 주기로 했다. 관악산의 등산로는 1부터 N까지의 서로 다른 번호가 붙어 있는 N개의 쉼터와 두 쉼..
28333번: 화이트 칼라 전미 최고의 사기꾼. 안 해본 도둑질, 안 해본 사기가 없는 닐 카프리는 오늘 저녁 세계 최고의 미술품 중 하나인 “뮤직박스”를 훔칠 예정이다. 오늘 아침, 이 정보를 입수한 AdbyMe, Inc. 는 그를 www.acmicpc.net BFS + BFS 제목 화이트 칼라 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 전미 최고의 사기꾼. 안 해본 도둑질, 안 해본 사기가 없는 닐 카프리는 오늘 저녁 세계 최고의 미술품 중 하나인 “뮤직박스”를 훔칠 예정이다. 오늘 아침, 이 정보를 입수한 AdbyMe, Inc. 는 그를 검거하기 위한 작전을 세우고 있다. AdbyMe, Inc. 는 그가 현재 어느 도시에 있는지, 그리고 뮤직박스가 어느 도시에 있는지 파악했고, ..
18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 배낭 문제 블럭의 개수가 오름차순으로 주어지지 않는다. 제목 함께 블록 쌓기 조건 시간 제한 : 1 초 메모리 제한 : 256 MB 문제 1번부터 N번까지의 학생들은 각각 블록들을 가지고 있다. 학생마다 최대 M개의 블록을 가지고 있을 수 있으며, 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르다. 이 때 1번부터 N번까지의 학생들이 가진 블록을 차례대로 사용하여 바닥에서부터 쌓아올려 하나의 탑을 만들고자 한다...
30045번: ZOAC 6 2023년 9월, 여섯 번째로 개최된 ZOAC의 오프닝을 또 맡은 성우는 영과일의 마스코트인 영일이를 이용해 대회를 홍보하기로 했다. 성우는 홍보 글이 주어질 때 각 문장에 01 또는 OI가 포함되어 있다 www.acmicpc.net 문자열 순회 제목 ZOAC 6 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 2023년 9월, 여섯 번째로 개최된 ZOAC의 오프닝을 또 맡은 성우는 영과일의 마스코트인 영일이를 이용해 대회를 홍보하기로 했다. 성우는 홍보 글이 주어질 때 각 문장에 01 또는 OI가 포함되어 있다면 문장 끝에 한 개의 영일이 이모티콘을 넣기로 했다. 이때, 홍보 글에 영일이 이모티콘을 총 몇 번 넣어야 하는지 구하여라. 입력 첫 번째 줄에 홍보 글..
2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 백트래킹 제목 스도쿠 조건 시간 제한 : 2 초 메모리 제한 : 256 MB 문제 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자. 위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜..
1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 세그먼트트리 : 최소 Height를 갖는 Index 저장 분할 정복 : 최소 Height를 기준으로 왼쪽 범위, 오른쪽 범위 다시 분할 정복 제목 히스토그램 조건 시간 제한 : 0.7 초 메모리 제한 : 128 MB 문제 히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다. 이러한 히스토그..
16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 1부터 1,000,000까지 가능한 최대 길이 찾기 → 이분 탐색 제목 과자 나눠주기 조건 시간 제한 : 1 초 메모리 제한 : 256 MB 문제 명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다. 조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다. 그런..
11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net Ctrl + A / Ctrl + C를 눌렀을 때의 최댓값 갱신 제목 크리보드 조건 시간 제한 : 1 초 메모리 제한 : 256 MB 문제 크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다. 화면에 A를 출력한다. Ctrl-A: 화면을 전체 선택한다 Ctrl-C: 전체 선택..
28432번: 끝말잇기 첫 줄에 끝말잇기 기록의 길이 $N$ 이 주어집니다. $(1 \le N \le 100)$ 둘째 줄부터 다음 $N$개의 줄에는 끝말잇기의 기록 $S_1, \cdots, S_N$이 한 줄에 하나씩 주어집니다. 여기서, 하나의 $S_i$는 “?” 로 www.acmicpc.net ?가 처음 단어인지, 끝 단어인지, 중간 단어인지 그리고 중복이 없는 지 제목 끝말잇기 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 끝말잇기는 단어를 중복하지 않고 단어의 맨 끝 글자에 이어서 말하는 놀이입니다. 끝말잇기 기록은 단어들의 나열로 이루어집니다. 올바른 끝말잇기 기록은 각 단어의 마지막 글자가 다음 단어의 첫 글자이며, 단어가 중복되어서 나타나면 안 됩니다. 끝말잇기 기록이 주어지는..
28431번: 양말 짝 맞추기 $6$이 쓰여 있는 양말 두 개를 한 짝으로, $8$이 쓰여있는 양말 두 개를 한 짝으로 만들면 $3$이 남습니다. www.acmicpc.net 해시셋 제목 양말 짝 맞추기 조건 시간 제한 : 0.5 초 메모리 제한 : 1024 MB 문제 양말 5개가 주어집니다. 각 양말에는 숫자가 하나씩 쓰여있습니다. 같은 숫자가 쓰인 양말 두 개를 모으면 양말 한 쌍이 됩니다. 쌍을 만들 수 있는 양말을 두 개씩 두 쌍 빼면 남는 양말에 쓰인 숫자는 무엇인가요? 입력 각 양말에 쓰인 숫자 5개가 한 줄에 하나씩 주어집니다. 입력으로 주어지는 모든 숫자는 0 이상 9 이하입니다. 항상 양말을 두 개씩 두 쌍 만들 수 있는 입력만 주어집니다. 출력 첫 줄에 남는 양말에 쓰인 숫자를 출력하세..
16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 구현 제목 배열 돌리기 3 조건 시간 제한 : 2 초 메모리 제한 : 512 MB 문제 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → 7 4 6 2 3 1 7 4 6 2 3 ..
11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 2개의 우선순위 큐 제목 절댓값 힙 조건 시간 제한 : 1 초 메모리 제한 : 256 MB 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N..
