본문 바로가기

문제 노트

 (157)
수 고르기( BOJ 20186 ) 문제 : https://www.acmicpc.net/problem/20186 20186번: 수 고르기 첫 번째 줄에 주어진 N개의 수 중 K개의 수를 고를 때, 전체점수의 최댓값을 출력한다. www.acmicpc.net 문제 파악하기 적절하게 K개의 숫자를 선택하여 얻을 수 있는 점수의 최댓값을 구하는 문제입니다. 점수는 선택한 K개의 숫자에서 얻을 수 있으며, 현재 숫자를 기준으로 왼쪽에 있는 숫자 중 선택된 수의 개수를 현재 숫자에서 뺀 값을 의미합니다. 어떻게 하면 점수를 최대로 만들 수 있을까요? 확인하는 방법은 여러가지 있습니다. 문제 해결하기 가장 떠올리기 쉬운 방법은 모든 경우의 수를 찾아보는 것입니다. 문제를 함수를 사용하여 상태로 추상화하면 우리는 무식하지만 확실하게 모든 경우의 수를 확..
종이접기( BOJ 20187 ) 문제 : https://www.acmicpc.net/problem/20187 20187번: 종이접기 접힌 종이를 접은 순서의 역순으로 펼친 후 정사각형에 뚫린 구멍의 위치를 번호로 출력한다. 출력은 총 2k줄로 이루어지며 i (1 ≤ i ≤ 2k)번째 줄에는 격자의 i번 행에 뚫린 구멍의 번호를 왼쪽 www.acmicpc.net 문제 파악하기 2N*2N 크기의 종이를 접은 다음 모서리 부근에 구멍을 하나 뚫었을 때, 구멍이 뚫리는 모든 위치를 출력하는 문제입니다. 항상 가로, 세로 각각 K번씩 접는다고 명시했기 때문에 종료 조건을 따로 설정할 필요가 없으며, 예외 사항을 생각하지 않아도 됩니다. 이 문제는 현재 종이의 모습을 적절하게 추상화한 다음, 종이가 접힌 역순으로 시뮬레이션하면 문제를 해결할 수 ..
금광( BOJ 10167 ) 문제 : https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이 www.acmicpc.net 문제 파악하기 x축과 y축에 평행한 직사각형 모양의 땅(R)에서 얻을 수 있는 최대 개발 이익을 구하는 문제입니다. R의 크기는 원하는 만큼 조정할 수 있으며, R의 범위 안에 있는 금광의 이익/손해를 모두 더한 값인 개발 이익이 될 수 있는 최댓값을 구해야 합니다. 금광의 위치가 1차원으로 이루어진 경우에는 1차원 배열을 이용한 연속된 구간의 최대합을 ..
쇼핑몰( BOJ 17612 ) 문제 : https://www.acmicpc.net/problem/17612 17612번: 쇼핑몰 입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 www.acmicpc.net 문제 파악하기 N명의 고객이 K개의 계산대에서 계산을 마치고 나가는 순서를 구하는 문제입니다. N명의 고객을 모든 계산대 뒤에 배치하기보다는 1줄로 기다리다가 비어있는 계산대에 배치한다고 생각하면 문제를 단순화시킬 수 있습니다. K개의 계산대 중 가장 먼저 계산이 끝나는 계산대를 구하는 효율적인 방법으로는 우선순위 큐를 사용할 수 있습니다. 우선순위 큐를 ..
계산 로봇( BOJ 22342 ) 문제 : https://www.acmicpc.net/problem/22342 22342번: 계산 로봇 M개의 행(가로줄)과 N개의 열(세로줄)이 있는 격자의 각 칸에는 로봇이 있다. 각 행에는 위에서부터 아래로 1부터 M까지의 번호가 붙어 있고, 각 열에는 왼쪽에서부터 오른쪽으로 1 부터 N까지의 www.acmicpc.net 문제 파악하기 문제를 이해하는데 가장 오랜 시간이 걸린 문제입니다. 설명이 조금은 난해하지만 차근차근 따라오면 문제는 쉽게 해결할 수 있습니다. 우선, 로봇에게는 3개의 값이 존재하는데 각각 입력값 / 저장값 / 출력값 이라고 부릅니다. 각각에 대해 하나씩 알아봅시다. 우선 입력값은 다른 로봇들의 출력값을 의미합니다. 다만, 모든 로봇이 아닌 특정 위치에 있는 로봇들의 출력값을 말합..
지우개( BOJ 21756 ) 문제 : https://www.acmicpc.net/problem/21756 21756번: 지우개 $N$개의 칸에 $1$ 부터 $N$ 까지의 수들이 왼쪽부터 순서대로 저장되어 있다. 또, 각 칸은 왼쪽부터 $1$ 부터 $N$까지 순서대로 번호가 붙어 있다. 즉, 처음에는 각 칸의 번호와 각 칸에 저장된 수가 www.acmicpc.net 문제 파악하기 기본적인 구현 문제입니다. 각 숫자의 특징을 파악해서 해결할 수도 있고, 큐 혹은 배열을 사용하여 해결하는 방법도 있습니다. 문제 해결하기 우선 자료구조(큐, 배열 등...)를 사용하는 방법에 대해 살펴봅시다. 이렇게 직접 숫자들을 가지고 매 작업을 시뮬레이션하기 위해서는 동일한 자료구조 2개가 필요합니다. 각각은 현재 값이 저장된 공간과 새롭게 값을 저장할..
나누기( BOJ 21757 ) 문제: https://www.acmicpc.net/problem/21757 21757번: 나누기 $N$개의 정수 수열 $A_1, A_2, \dots , A_N$이 주어진다. 수열을 각각이 연속된 네 부분으로 나누려고 한다. 단, 각 부분은 최소 하나의 수를 포함해야 한다. 또, 각 부분의 합은 모두 같아야 한다. 즉, 어 www.acmicpc.net 문제 파악하기 N개의 숫자를 정확히 4등분으로 나누는 문제입니다. 나누어진 부분의 합이 모두 동일해야 한다는 조건이 있는데 이 조건에 초점을 맞추면 문제를 해결할 수 있습니다. 4개의 부분합이 모두 동일하기 위해서는 각각의 부분합은 (전체 N개 숫자의 누적합)/4의 값을 만족합니다. 이는 단순하게 생각하면 도출할 수 있는 결론입니다. 이를 통해 우리는 나올 ..
지그재그 서기( BOJ 1146 ) 문제 : https://www.acmicpc.net/problem/1146 1146번: 지그재그 서기 첫째 줄에 총 경우의 수를 1,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 파악하기 학생들을 특정 규칙에 맞춰 줄을 세우는 문제입니다. 여기서의 규칙은 학생들의 키가 커졌다, 작아졌다를 반복하게 만들어야 한다는 것입니다. 예를 들어 { 1 3 2 4 } 또는 { 4 2 3 1 }과 같이 학생이 커졌다가 작아졌다가를 반복하게 줄을 서야하며, { 1 2 3 4 } 혹은 { 3 4 2 1 }과 같이 계속 작아지거나 커지는 경우가 있으면 안됩니다. 이렇게 줄을 세우는 경우의 수를 구하기 위해서는 어떤 방법이 있을까요? 문제 해결하기 우선, 문제를 추상화할 필요가 있습니다. 문제에..

티스토리툴바