wgrgwg-dev

13397 : 구간 나누기 2https://www.acmicpc.net/problem/13397 문제N개의 수로 이루어진 1차원 배열이 있다. 이 배열을 M개 이하의 구간으로 나누어서 구간의 점수의 최댓값을 최소로 하려고 한다. 구간은 다음과 같은 조건을 만족해야 한다.하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다.배열의 각 수는 모두 하나의 구간에 포함되어 있어야 한다.구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다. 예를 들어, 배열이 [1, 5, 4, 6, 2, 1, 3, 7] 이고, M = 3인 경우가 있다.이때, [1, 5], [4, 6, 2], [1, 3, 7]로 구간을 나누면 각 구간의 점수는 4, 4, 6점이 된다. 이때, 최댓값은 6점이다.만약, [1, 5, 4], [..

15988 : 1, 2, 3 더하기 3https://www.acmicpc.net/problem/15988 문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.기본적인 dp 문제였다. 문제정의..

3649 : 로봇 프로젝트https://www.acmicpc.net/problem/3649 문제상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다. 구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다. 지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오.입력입력은 여러 개의 테스트 케이스로 이루어져 있다.각 테스트 케..

1105 : 팔https://www.acmicpc.net/problem/1105 문제L과 R이 주어진다. 이때, L보다 크거나 같고, R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 수에 들어있는 8의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다.출력첫째 줄에 L보다 크거나 같고, R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 수에 들어있는 8의 개수를 구하는 프로그램을 작성하시오.언뜻보면 어려워보이지만, 그리디로 잘 생각하면 쉬운 문제이다. 두 수 L, R이 주어졌을 때, 먼저 두가지 경우로 나눠서 생각해보자. 두 수의 ..

1309 : 동물원https://www.acmicpc.net/problem/1309 문제어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.입력첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.출력첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.dp 문제라는 것을..

1174 줄어드는 수https://www.acmicpc.net/problem/1174 문제음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.입력N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.출력첫째 줄에 N번째 작은 줄어드는 수를 출력한다.먼저 큐에 0~9까지의 수를 삽입한다.그 후, 큐에서 숫자를 하나씩 꺼내서, 그 수에서 한자리를 추가해서 만들 수 있는 수들(감소하는 수)을 큐에 추가해준다...

12869 뮤탈리스크https://www.acmicpc.net/problem/12869 문제수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.첫 번째로 공격받는 SCV는 체력 9를 잃는다.두 번째로 공격받는 SCV는 체력 3을 잃는다.세 번째로 공격받는 SCV는 체력 1을 잃는다.SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.남아있는 SCV의 체력이 주어졌을..

2211 : 네트워크 복구https://www.acmicpc.net/problem/2211 문제N(1 ≤ N ≤ 1,000)개의 컴퓨터로 구성된 네트워크가 있다. 이들 중 몇 개의 컴퓨터들은 서로 네트워크 연결이 되어 있어 서로 다른 두 컴퓨터 간 통신이 가능하도록 되어 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다. 각 컴퓨터들과 회선은 그 성능이 차이가 날 수 있다. 따라서 각각의 직접 연결되어 있는 회선을 이용해서 통신을 하는데 걸리는 시간이 서로 다를 수 있다. 심지어는 직접 연결되어 있는 회선이 오히려 더 느려서, 다른 컴퓨터를 통해서 통신을 하는 것이 더 유리할 수도 있다. 직접 연결되어 있는 회선을 사용할 경우..