전체 글

문제 설명수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.https://www.acmicpc.net/problem/10986      제한 사항      풀이문제를 요약하면, 연속한 부분의 합이 M으로 나누어 떨어지는 (i, j)의 쌍의 개수를 구하는 것이다. 누적합을 이용하면 간단하게 풀 수 있어 보이지만 사실은 그렇지 않다.누적합을 이용하여 (i, j)의 모든 쌍을 구한다고 가정하면 N이 최대 $10^6$이기 때문에 시간초과가 발생한다.따라서, 다른 풀이가 필요하다. 문제의 핵심은 mod연..

문제 설명수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.https://www.acmicpc.net/problem/12738      제한 사항      풀이문제를 요약하면, 주어진 배열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 것이다.유명한 DP문제인 LIS를 구현하면 된다. 하지만, 해당 문제의 난도가 높게 평가된 이유는 아마 시간 초과를 해결해야 하기 때문이다.보통의 LIS는 $O(N^2)$의 시간복잡도를 갖는다.i번째 이전의 수중 i번째 수보다 더 작은 수가 갖고 있는 가장..

문제 설명두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.자연수 N이 주어졌을 때, g(N)을 구해보자.https://www.acmicpc.net/problem/17425      제한 사항      풀이문제를 요약하면, T개의 x가 주어졌을 때, x보다 작은 수들의 약수의 합을 구해야 한다.즉, 1부터 x까지 모든 수에 대해 약수를 구하고 그를 모두 더한 값을 구해야 하는 것이다. 간단하게는 모두..

문제 설명선종이는 최근에 배열을 정렬하는 새로운 알고리즘을 이길흥 교수님의 강의에서 배웠습니다. 그 알고리즘은 배열의 숫자들을 반복적으로 삭제, 삽입을 수행하여 배열을 정렬합니다. 선종이는 이 정렬 알고리즘을 삭삽 정렬이라 이름 붙였습니다. 삭삽 정렬은 다음과 같은 과정을 수행합니다.배열의 요소 하나를 선택합니다.배열에서 해당 요소를 삭제합니다.해당 요소를 배열의 맨 뒤에 삽입합니다.선종이는 호기심이 많은 학생이기 때문에, 삭삽 정렬을 수행하여 배열을 정렬 할 때 가장 적게 위와 같은 삭삽 과정이 얼마나 수행되는지 알아보고 싶어졌습니다.https://www.acmicpc.net/problem/13884      제한 사항      풀이문제를 요약하면, 배열이 주어졌을 때 하나의 숫자를 택해 제일 뒤로 보..

문제 설명상근이는 친구들과 함께 라인제로 스키장에 왔다. 오전, 오후에는 열심히 스키를 타고, 저녁 때는 근처 바로 가서 술을 마시며 친구들과 놀려고 한다.라인제로 스키장은 모든 시설이 세계 최고를 자랑하지만, 한 가지 단점이 있다. 바로, 스키 리프트이다. 리프트는 너무 작아서 5초에 한 명씩 태울 수 있다.보통 친구와 동시에 스키장의 정상에서 내려온다고 해도, 리프트가 있는 곳에는 동시에 도착하지 않는다. 따라서, 리프트를 타기 전에 친구가 내려오기를 기다려야 하고, 리프트에서 내린 이후에도 친구가 내리기를 기다려야 한다.상근이는 친구가 아직 리프트에 도착하지 않았다면, 줄을 뒤에 있는 사람에게 양보하려고 한다. 상근이의 입장에서 이 상황을 살펴 보면, 상근이가 아낄 수 있는 시간은 없고, 기다리는 ..

문제 설명아래의 그림과 같이 배열된 장애물들 사이로, 구슬을 굴린다.장애물들은 n개의 행에 걸쳐 배치되어 있으며, 구슬은 맨 위의 행부터 맨 아래의 행을 향해 구른다. 각 행의 장애물들을 지나면서, 구슬은 왼쪽 또는 오른쪽으로 굴러갈 수 있다. 각 행의 번호는 0부터 n-1까지로 주어지며, 그 행의 장애물 사이의 공간은 왼쪽부터 차례로 0으로 주어진다.(0, 0)의 위치에서부터 아래로 구슬을 굴려갈 때, n-1번 행까지 구슬을 굴리는 경우의 수를 구하는 프로그램을 작성하시오. 단, 구슬은 주어진 m개의 공간을 모두 지나야 한다.https://www.acmicpc.net/problem/23317      제한 사항      풀이문제를 요약하면, 주어진 좌표에 해당하는 빈칸을 모두 통과하여 바닥까지 떨어지는..

문제 설명회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다. 새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.원래 회전 초밥은 손님이 마음대로 초밥을  고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종..