본문 바로가기

문제 노트/백준

 (102)
Ignition( BOJ 13141 ) 문제 : https://www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 문제 파악하기 모든 간선을 불 태우는데 걸리는 최소 시간을 구하는 문제입니다. 보통 그래프 문제들은 정점에 초점을 맞췄다면 이번 문제는 간선에 초점을 맞춘 문제라고 할 수 있습니다. 간선은 인접한 정점에 불이 붙으면 1초에 1씩 불타며, 양 끝의 정점이 모두 불이 붙었다면 양쪽에서 불타게 됩니다. 문제를 해결하기 위해서는 어떤 정점..
임계경로( BOJ 1948 ) 문제 : https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 문제 파악하기 임계경로의 길이 및 임계경로에 해당하는 간선의 개수를 구하는 문제입니다. 월드 나라를 그래프로 직접 표현해보면 시작과 종료 정점이 정해져있으며, 싸이클이 없는 그래프로 그려지기 때문에 손쉽게 임계 경로를 구하는 문제라는 걸 눈치챌 수 있습니다. 다만, 임계 경로에 해당하는 간선의 개수를 세기 위해서는 약간의 알고리즘이 필요합니다. 문제 해결하기 우..
보석 모으기( BOJ 1480 ) 문제 : https://www.acmicpc.net/problem/1480 1480번: 보석 모으기 첫째 줄에 보석의 개수 N, 가방의 개수 M, 가방의 최대 한도 C가 주어진다. N은 1보다 크거나 같고, 13보다 작거나 같은 자연수이고, M은 1보다 크거나 같고, 10보다 작거나 같은 자연수이다. C는 1보 www.acmicpc.net 문제 파악하기 N개의 보석을 M개의 가방에 적절하게 넣어서 챙길 수 있는 보석의 최대 개수를 구하는 문제입니다. 각각의 보석은 1~20그램의 무게를 가지며, 가방에는 최대 C그램의 보석을 담을 수 있습니다. 만약 가방이 한 개라면 입력되는 범위 값이 작기 때문에 브루트 포스 알고리즘으로 충분히 해결할 수 있지만, 가방이 최대 10개까지 있을 수 있기 때문에 좀 더 효율..
오아시스 재결합( BOJ 3015 ) 문제 : https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 문제 파악하기 N명의 사람 중 서로를 볼 수 있는 사람이 총 몇 명인지 구하는 문제입니다. 서로를 볼 수 있다는 의미는 두 사람 사이에 어느 누구보다도 큰 사람이 없다는 의미입니다. 즉, 어느 한 사람만 볼 수 있는 경우는 제외해야 합니다. 예를 들어, 3명의 사람이 [ 6 5 4 ] 순서로 서있다고 가정해봅시다. 이 경우 가장 맨 앞의 사람(6)은 나머지 사람들(..
Parcel( BOJ 16287 ) 문제 : https://www.acmicpc.net/problem/16287 16287번: Parcel 입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가 www.acmicpc.net 문제 파악하기 N개의 숫자 중 4개의 서로 다른 숫자의 합이 정확하게 W를 만족하는 경우가 있는지 찾는 문제입니다. N의 값이 최대 5,000이라 작은 편이지만 모든 경우의 수를 탐색하는 O(N4) 알고리즘을 사용하기에는 충분히 큰 숫자입니다. 따라서, 적절한 탐색 기법을 활용해 O(N2) 알고리즘으로 바꾸어야 합니다. 어떻게 해야 알고리즘..
책 페이지( BOJ 1019 ) 문제 : https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 파악하기 1 페이지부터 입력된 N 페이지까지 모든 페이지에서 등장한 숫자(0-9)의 개수를 구하는 문제입니다. N의 범위가 작다면 반복문을 활용하여 쉽게 구할 수 있지만 최대 10억까지 입력될 수 있기에 단순히 반복문으로는 구할 수 없습니다. 이 경우, N을 잘게 나눠서 문제를 해결할 수 있습니다. 문제 해결하기 N을 어떻게 나눌 수 있을지 생각해보는 건, 어떤 상황일 때 숫자의 개수를 구하기 쉬운지 생각하면 됩니다. 만약 N이 1234라면 어떻게 ..
최대공약수들( BOJ 10244 ) 문제 : https://www.acmicpc.net/problem/10244 10244번: 최대공약수들 n개의 수로 이루어진 수열 A가 주어질 때, 1≤lo≤hi≤n의 정의역을 가지는 함수 f(lo,hi)는 Alo부터 Ahi까지 모든 원소들의 최대공약수로 정의된다. lo와 hi는 수열의 원소가 아닌 인덱스라는 점에 주 www.acmicpc.net 문제 파악하기 f(lo, hi)를 A[lo] ~ A[hi] 사이의 모든 숫자의 최대공약수라고 할 때, f(lo, hi)의 값이 될 수 있는 모든 경우의 수를 구하는 문제입니다. 수열의 길이는 최대 100,000이기에 모든 구간을 확인할 수는 없지만 다행히 수열의 원소 값인 a의 범위는 1~100 사이의 정수로 범위가 작습니다. 이 점을 활용하면 문제를 해결할 수..
홍준이의 친위대( BOJ 3948 ) 문제 : https://www.acmicpc.net/problem/3948 3948번: 홍준이의 친위대 홍준 왕국의 국왕 홍준이는 자신을 호위하는 N명의 친위대 병사가 있다. 병사들의 키는 모두 다르다. 홍준이는 그들을 일렬로 세울 때, 키 순서대로 세우는 것보다 맨 끝 두 병사를 제외한 나머 www.acmicpc.net 문제 파악하기 N개의 숫자를 규칙에 맞게 세우는 경우의 수를 구하는 문제입니다. 통칭 지그재그 수열이라고 불리는 이 수열의 가짓수를 세는 방법에는 여러가지가 있지만, 점화식을 사용하여 가짓수를 구하는 방법을 사용해보겠습니다. 문제 해결하기 홍준이가 원하는 방식으로 나열한 N개의 숫자는 두 번째 숫자의 크기에 따라 2가지 종류로 구분할 수 있습니다. 두 번째 숫자는 첫 번째 숫자보다 클 ..

티스토리툴바