문제 링크https://www.acmicpc.net/problem/1564 문제 요약\(N\)이 주어졌을 때, \(N!\)의 마지막 0이 아닌 5자리 수를 출력하는 문제이다. 예를 들어, \(N\)이 10인 경우 \(10!\)은 3628800이며, 마지막 0이 아닌 5자리 숫자는 36288이 된다. 문제 풀이BigInt와 같은 큰 수 자료형을 사용해 팩토리얼을 직접 계산하기 위해서는 많은 시간과 공간 복잡도가 필요하다. 따라서 더 효율적인 방법이 필요하다. 얼핏 보면 팩토리얼의 마지막 다섯 자리만 유지하면 될 것 같지만, 팩토리얼 값의 끝에 붙는 0, 즉 트레일링 제로를 제거하고 출력해야 하기 때문에 단순히 마지막 다섯 자리만 유지하는 것으로는 문제를 해결할 수 없다. 핵심은 트레일링 제로가 언제 생기는..
문제 링크https://www.acmicpc.net/problem/21925 문제 요약길이가 \(N\)인 수열이 \(A\)가 주어진다. 수열 \(A\)를 길이가 짝수인 부분 수열들로 나눌 때, 짝수 팰린드롬을 최대한 많이 만드는 문제이다. 문제 풀이이 문제는 부분 수열의 팰린드롬 여부를 미리 계산하는 전처리와 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있다. 1. 부분 수열의 팰린드롬 여부를 미리 계산하기부분 수열이 팰린드롬인지 여부를 나타내기 위해, boolean 타입의 2차원 배열 isPalindrome을 사용한다. 이 배열에서 isPalindrome[j][i]는 인덱스 \(j\)부터 \(i\)까지의 부분 수열이 팰린드롬인지를 나타낸다. 만약 가능한 모든 \(j\)와 \..
문제 링크https://www.acmicpc.net/problem/20040 문제 요약\(N\)개의 점이 있다. 이때 서로 다른 두 개의 점을 연결하는 선분들이 차례대로 주어졌을 때, 사이클이 생기는 순간을 찾는 문제이다. 문제 풀이각 점을 노드로, 선분을 간선으로 하는 무향 그래프로 모델링을 한다. 새로운 간선을 추가할 때마다 두 노드가 같은 집합에 속해 있는지 확인한다. 만약 같은 집합에 속해 있다면, 해당 간선을 추가하면 사이클이 형성되는 것이다. 반대로, 같은 집합에 속해있지 않으면 두 집합을 합쳐서 하나의 집합으로 만든다. 유니온 파인드(Union Find) 자료구조를 이용해 집합을 효율적으로 관리할 수 있으며, 제한시간 내에 문제를 해결할 수 있다. 소스 코드더보기더보기#include #inc..
문제 링크https://www.acmicpc.net/problem/17216 문제 요약주어진 수열 \(A\)에서 합이 가장 큰 감소하는 부분 수열을 찾는 문제이다. 문제 풀이감소하는/증가하는 부분 수열을 찾는 문제는 전형적인 동적 계획법(Dynamic Programming) 문제들 중 하나이다. 이 문제 역시 점화식을 세워 동적 계획법으로 문제를 해결할 수 있다. 점화식을 세우기 전에 DP 배열부터 정의를 해보자. \(dp[i]\)는 수열 \(A\)에서 \(A[i]\)로 끝나는 감소 부분 수열의 합 중에서 가장 큰 값을 저장하는 배열이다. 그다음으로 DP 배열을 초기화한다. 각 원소는 자기 자신만을 포함하는 감소 부분 수열이 될 수 있으므로, \(dp[i]\)의 초기값을 \(A[i]\)로 설정한다. 이제..
문제 링크https://www.acmicpc.net/problem/22742 문제 요약이팍이는 파티에서 여러 여자친구를 새롭게 사귀었고, 이들과 데이트 일정을 잡으려고 한다. 이삭이는 한 번에 한 명의 여자친구만 만날 수 있으며, 만날 수 있는 시간은 정해져 있다. 또한 각 여자친구마다 이삭이를 만날 수 있는 시간이 정해져 있다. 이 때 이삭이가 최적의 일정으로 스케줄링을 했을 때 최대한 만날 수 있는 여자친구들의 수를 구하는 문제이다. 문제 풀이이삭이가 사용할 수 있는 시간들을 왼쪽 노드로, 각 여자친구들을 오른쪽 노드로 설정하면 문제를 이분 그래프로 모델링 할 수 있다. 아래 그림은 예제 입력을 이분 그래프로 모델링 한 결과이다. 이제 문제는 이분 그래프에서 최대 매칭을 구하는 문제로 바뀌었고, 이분..
문제 링크https://www.acmicpc.net/problem/3632 문제 요약\(N\)개의 빨래와 각각의 빨래가 가지고 있는 초기 물의 양이 주어진다. 모든 빨래는 1분마다 물의 양이 1씩 줄어들며, 매 분마다 한 개의 빨래를 선택해 라디에이터에 올릴 수 있다. 라디에이터에 올린 빨래는 물의 양이 1분마다 \(K\)씩 줄어든다. 모든 빨래의 물의 양이 0이 되는 최소한의 시간을 구하는 문제이다. 문제 풀이만약 \(X\)분 내에 모든 빨래를 말릴 수 있는 방법이 존재한다면, \(X\)분보다 더 큰 시간 내에서도 모든 빨래를 말릴 수 있다. 반대로 \(X\)분 내에 모든 빨래를 말릴 수 없다면, \(X\)분 보다 더 작은 시간 내에 모든 빨래를 말릴 방법은 존재하지 않는다. 이 특성을 이용해 최적화 ..
문제 링크https://www.acmicpc.net/problem/17610 문제 요약이 문제는 서로 다른 무게의 추 \(k\) 개가 주어졌을 때, 양팔저울을 한 번만 사용하여 1부터 주어진 추들의 무게의 합인 \(S\) 사이의 모든 무게 중 측정이 불가능한 무게의 개수를 구하는 문제이다. 문제 풀이이 문제를 해결하기 위해서는 \(k\)개의 추를 가지고 만들 수 있는 모든 가능한 무게 조합을 고려하는 완전 탐색을 이용할 수 있다. 각 추에 대해 우리는 세 가지 선택을 할 수 있다.추를 사용하지 않는 경우양팔저울의 왼쪽에 올려놓는 경우양팔저울의 오른쪽에 올려놓는 경우각 추를 위와 같은 세 가지 선택지 중 하나로 결정한 후, 양팔저울의 왼쪽과 오른쪽에 놓인 추들의 무게 차이를 계산한다. 이렇게 계산된 모든 ..
문제 링크https://www.acmicpc.net/problem/17608 문제 요약일렬로 세워진 막대기를 오른쪽에서 바라봤을 때, 보이는 막대기의 수를 구하는 문제이다. 문제 풀이주어진 막대기들을 오른쪽에서 왼쪽으로 하나씩 살펴보는 방법으로 문제를 해결할 수 있다. 오른쪽 끝의 막대기부터 시작해서, 현재까지 본 막대기들 중 가장 높은 것과 현재 막대기의 높이를 비교한다. 만약 현재 막대기의 높이가 지금까지 본 막대기들 중 가장 높은 막대기의 높이보다 크다면, 그 막대기는 오른쪽에서 봤을 때 보이는 막대기이다. 이 과정을 가장 왼쪽에 있는 막대기까지 반복하면, 오른쪽에서 봤을 때 보이는 막대기의 수를 구할 수 있다. 소스 코드더보기더보기#include int n, A[100010];int main(..
문제 링크https://www.acmicpc.net/problem/32072 문제 요약문제에서 정의한 뽑아내기 연산을 수행할 때마다 루트에 있는 가중치의 값을 출력하는 문제이다. 뽑아내기 연산을 수행할 때는 특별한 경로를 찾아야 하는데, 한 정점에서 이동할 자식을 결정할 때는 직계 자식들만 비교하면 된다는 것에 유의하자. (한 정점의 자손들 중 가장 작은 가중치를 가지는 정점으로 이동하는 경로를 찾아야 하는 것으로 문제를 잘못 이해해 시간을 너무 많이 날렸다...🤦♂️) 문제 풀이뽑아내기 연산을 수행한다고 하지 말고, 루트 정점에 있어야 하는 정점들을 순회한다고 접근하면 문제를 조금 더 쉽게 풀 수 있다. 그렇다면 어떤 순서대로 정점을 방문해야 할까? 뽑아내기 연산을 할 때, 특별한 경로에 있는 정점..
문제 링크https://www.acmicpc.net/problem/25571 문제 요약길이가 \(N\)인 배열이 주어졌을 때, 만들 수 있는 연속된 부분배열들 중 지그재그인 부분배열의 개수를 찾는 문제이다. 배열이 지그재그라는 뜻은 배열의 원소가 감소와 증가 또는 증가와 감소를 반복하는 배열을 의미한다. 문제 풀이만들 수 있는 모든 부분배열 \(A[lo, hi]\)에 대해서 지그재그인지 검사하면 답을 구할 수 있다. 하지만 이 방법은 시간복잡도가 \(\mathcal {O}(N^2)\)이라서, \(N\)이 10만 일 때 제한시간 내에 문제를 해결하지 못하므로 더 효율적인 풀이가 필요하다. 지그재그 부분배열의 특징을 살펴보면 \(A[lo, hi - 1]\)이 지그재그이고, \(A[lo, hi]\)가 지그재..
문제 링크https://www.acmicpc.net/problem/32070 문제 요약같은 색깔의 공을 하나의 상자에 모으는 데 필요한 최소 이동 횟수를 구하는 문제이다. 각 상자는 최대 두 개의 공을 담을 수 있다. 공을 꺼낼 때는 상자의 위에 있는 공만 꺼낼 수 있으며, 공을 넣을 때는 빈 상자나 같은 색깔의 공이 있는 상자에만 넣을 수 있다. 문제 풀이같은 색깔의 공을 하나의 상자에 모으기 위해 공을 옮기다 보면 연쇄적으로 다른 공들도 움직여야 하는 상황이 발생한다. 이 과정에서 연쇄적으로 움직이는 공들을 추적하다 보면 하나 이상의 싸이클이 만들어지는 것을 발견할 수 있다.위 예시를 보면 1, 2, 3, 4번 공의 싸이클과 5, 6, 7번 공의 사이클은 답을 구하는 과정에서 서로 영향을 끼치지 않..
문제 링크https://www.acmicpc.net/problem/32069 문제 요약수직선 도로 위해 \(N\) 개의 가로등이 위치해 있다. 각 위치에서 가장 가까운 가로등까지의 거리를 계산하고, 그 거리들을 오름차순으로 정렬한 뒤 앞에서부터 \(K\) 개 출력하는 문제이다. 문제 풀이문제에서는 어두운 정도를 각 위치로부터 가장 가까운 가로등까지의 거리로 정의하고 있다. 그래서 처음에는 각 위치별로 가장 가까운 가로등까지의 거리를 모두 계산해야 한다고 생각할 수 있다. 하지만 도로의 길이 \(L\)이 최대 \(10^{18}\)까지 될 수 있기 때문에, 모든 위치를 전부 탐색하는 완전탐색은 사실상 불가능하다. 이 문제를 해결하기 위해서는 가로등을 기준으로 생각할 필요가 있다. 각 가로등들을 중심으로 가까..
