본문 바로가기

문제 노트/정올

 (47)
지우개( 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 6986 ) 문제 : https://www.acmicpc.net/problem/6986 6986번: 절사평균 첫째 줄에 절사평균(N, K)를, 둘째 줄에 보정평균(N, K)를 각각 소수점이하 셋째 자리에서 반올림하여 둘째 자리까지 출력한다. 예를 들어 결과값이 9.667인 경우 9.67로, 5인 경우 5.00으로, 5.5인 경우 www.acmicpc.net 문제 파악하기 체조경기에서 사용하는 평균 계산법인 절사평균과 보정평균을 구하는 문제입니다. 다만, 입력이 실수로 주어지기 때문에 오차가 발생하기 쉽다는 점을 간과한다면 절대 풀 수 없는 문제입니다. 절사평균과 보정평균을 구하는 방법은 간단합니다. 모든 입력값을 정렬한 다음, 양 쪽의 K개 숫자를 없애거나(절사평균) K개 숫자를 인근 숫자로 변환(보정평균)한 다음,..
배수( BOJ 2595 ) 문제 : https://www.acmicpc.net/problem/2595 2595번: 배수 N은 30,000이하의 자연수이다. www.acmicpc.net 문제 파악하기 30,000 이하의 자연수인 N의 배수 중 가장 적은 개수의 숫자로 이루어진 가장 작은 배수를 찾는 문제입니다. 예를 들어 125의 배수는 무한히 많은 숫자가 있지만, 그 중에서 가장 적은 개수의 숫자로 이루어진 가장 작은 배수는 500을 의미합니다. 이 문제는 결국 1개 또는 2개의 숫자로 이루어진 N의 배수가 있는지, 그리고 그 중에서 가장 작은 숫자가 무엇인지 구하는 문제입니다. 참고로 모든 정수는 1개 혹은 2개의 숫자로 이루어진 배수를 무조건 가지고 있습니다. 문제 해결하기 우리는 그렇다면 0~9까지 숫자 중 2가지를 뽑아서 ..
모빌 이진수( BOJ 2471 ) 2471. 모빌 이진수 : https://www.acmicpc.net/problem/2471 2471번: 모빌 이진수 첫째 줄에는 0, 1과 괄호들로 구성된 모빌의 상태 표현이 주어진다. 모빌의 상태 표현은 빈칸 없이 이어진 문자열로 주어진다. 주어지는 0, 1과 괄호들의 총 개수는 200개 이하이다. 둘째 줄에는 K www.acmicpc.net 문제 파악하기 0과 1로 이루어진 이진수가 주어집니다. 괄호 안의 값은 회전할 수 있으며, 회전 시 괄호 안의 숫자들은 뒤집히게 됩니다. 주어진 이진수로 만들 숫자 중 K번째 숫자를 찾아야 합니다. 입력되는 숫자와 괄호의 길이는 최대 200개이기 때문에 문자열로 입력을 받아야 합니다. 메모리의 제한 때문에 만들 수 있는 모든 문자열을 저장할 수는 없습니다. 그럼..
양팔 저울( BOJ 1653 ) 문제 1653. 양팔 저울 : https://www.acmicpc.net/problem/1653 1653번: 양팔 저울 무게가 서로 다른 추들의 집합이 주어진다. 각 추의 무게는 1g 이상 9g 이하의 정수이다. 이 추들 중에서 몇 개를 선택하여 양팔저울에 올려서 평형을 만들고자 한다. 양팔저울에는 양쪽에 5개씩 www.acmicpc.net 문제 파악하기 추는 1g, 2g, ... , 9g까지 최대 9개가 있습니다. 양팔 저울에는 눈금이 5개씩 있으며, 평형을 이루게 만드는 추의 배치를 '평형정수'로 표현할 수 있으며, K번째 평형정수를 찾아야 합니다. 단순히 첫 번째 위치부터 추를 하나씩 놓으면 시간초과에 걸릴 수 있습니다. 어떤 방법으로 탐색을 해야 할까요? 문제 해결하기 추를 놓은 위치는 00001..
체인점( BOJ 2472 ) 문제 2472. 체인점 : https://www.acmicpc.net/problem/2472 2472번: 체인점 첫째 줄에는 매장 후보지의 개수를 나타내는 정수 N이 입력된다(1≤N≤100,000). 매장 후보지들은 1부터 N까지의 번호로 구분된다. 둘째 줄에는 아파트 단지의 위치를 나타내는 세 개의 정수 A, B, C www.acmicpc.net 문제 파악하기 아파트는 A, B, C로 총 3개의 노드가 주어집니다. 후보지 p에서 A, B, C까지의 거리가 후보지 q에서 A, B, C까지의 거리보다 모두 먼 경우, 후보지 p에는 매장을 설치하지 않습니다. 후보지에 매장을 설치할 수 있는지 여부를 알기 위해서는 후보지마다 A, B, C까지의 거리를 구해야 합니다. 거리는 음수가 나오지 않기에 가장 빠른 다..

티스토리툴바