본문 바로가기

개발/알고리즘

 (30)
일방통행 문제 1 에서 출발하여 N 까지 최소 길찾기, 길은 일방통행 임 각 노드는 빨걍, 파랑, 그린, 흰색을 가지는데 노드의 색깔이 빨강색이면 빨강색 통행증 제출 (빨강색 통행증이 없으면 나갈 수 없음) 파랑색이면 파랑색 통행증 제출 (파랑색 통행증이 없으면 나갈 수 없음) 그린이면 그대로 통과 흰색이면 통행증 지급, 단 통행증은 각각 1개를 초과할 수 없다. 출발시 빨간 통행증랑1 파란 통행증 1을 가지지고 출발한다. 1에서 N까지 최소 길을 찾는 문제 입력 테스트 개수 노드의 수 1
마트료시카 문제 동현이는 인형을 좋아한다. 이러한 동현이를 위해 마트료시카를 선물해주자. 마트료시카는 러시아 전통 인형으로 인형 안의 인형을 넣을 수 있는 인형이다. 인형들이 열렬로 늘어서 있다. 인형들마다 크기가 주어져 있는데, 앞에 있는 인형의 크기가 뒤에 있는 인형의 크기보다 작으면, 앞에 있는 인형을 뒤에 있는 인형 안에 넣을 수 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 인형이 있다면, 크기 1인 인형을 크기 5인 인형에 넣고, 다시 이 인형들을 크기 7인 인형 안에 넣을 수 있다. 하지만 이렇게 인형를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 인형들을 선택하면 총 4개의 인형이 한 개의 인형에 들어가게 된다..
폐지줍기 문제 N×N 격자로 이루어진 도시가 있다. 이 도시 군데군데에는 폐지가 버려져 있다. 범수는 가장 왼쪽 위 격자 (1, 1)에서 출발하여 가장 오른쪽 아래 격자 (N, N)까지 이동하며 폐지를 줍는데, 최단 경로를 따라가야만 한다. 즉, 인접한 오른쪽 칸 또는 아래쪽 칸으로만 이동할 수 있다. 이 때, 범수가 수집할 수 있는 폐지의 최대값을 출력하시오. 출발점과 도착점에 위치한 폐지 또한 주울 수 있다. 입력 첫 번째 줄에는 도시의 크기 N이 주어진다. (2 ≤ N ≤ 200) 두 번째 줄부터 N개의 줄에 걸쳐 도시의 정보가 주어진다. 도시의 정보 중 i번째 줄의 j번째 숫자는 격자 (i, j)에 버려진 폐지의 양 A_ij을 나타낸다. (0 ≤ A_ij ≤ 1000) 출력 범수가 주울 수 있는 최대 폐지..
합분해 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫 번째 줄에 두 정수 N, K가 공백으로 분리되어 주어진다. (1 ≤ N, K ≤ 200) 출력 첫 번째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 힌트 예제 입력 20 2 예제 출력 21 #include #include using namespace std; //D[i][j] = i개의 수를 더해서 j를 만드는 경우의 수 //D[i][j] = sum of D[i-1][j-k] for all 0 5개 //D[2][3] = 0:3, 1:2, 2:1, 3..
롤러코스터 문제 소들은 롤러코스터를 짓고있다! 소들은 자신들이 가지고 있는 돈을 활용해서 최대한 재밌는 롤러코스터를 만들고 싶어한다. 롤러코스터는 직선형으로, 길이가 L이다. 소들이 롤러코스터를 지을 때, 롤러코스터는 N개의 교체 가능한 부품들중 일부로 구성되어야 한다. 각 부품 i는 고정된 길이 Wi를 가지고 있다. 그리고 다양한 지형의 굴곡 때문에, i번째 부품은 오직 Xi의 위치를 시작점으로만 놓을 수 있다. 소들은 다양한 롤러코스터를 0부터 L까지 빈틈없이 채우고 싶어한다. 만약 중간에 빈칸이 있으면 롤러코스터를 구성할 수 없다. 또한, 각 부품끼리 겹쳐서 롤러코스터를 건설하는 경우도 없다. 각 i번째 부품은 "재미도" Fi과 짓는데 드는 비용 Ci가 있다. 총 비용은 롤러코스터를 구성하는 부품을의 비용의 ..
인접한 비트의 개수 문제 0과 1로 이루어진 수열 S가 주어진다. S의 첫 수를 s_1, 마지막 수를 s_N이라고 할 때, S의 인접한 비트의 개수는 다음과 같이 구할 수 있다. s_1 x s_2 + s_2 x s_3 + s_3 x s4 + ... + s(N-1) x s_N 위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다. 수열 S의 크기 N과 K가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오. 예를 들어, N이 5이고, K가 2이면, 수열 S가 될 수 있는 수열은 다음과 같이 6가지가 있다. 11100 01110 00111 10111 1110..
이친수 문제 0과 1로 이루어진 이진수 중 다음 성질을 만족하는 수를 이친수라고 한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면, 1, 10, 100 등이 이친수가 된다. 하지만 010이나 110은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다. N이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 90) 출력 첫 번째 줄에 N자리 이친수의 개수를 출력한다. 힌트 예제 입력 3 예제 출력 2 #include #include using namespace std; int N; long long A[91]; int main() { //ifstrea..
계단 오르기 문제 최대 2 칸 까지 오를 수 있을 때 오르는 방법의 가짓수를 생각해 보자. 아래 그림은 n 이 4 인 경우의 예 이다. 총 5가지 경우가 존재한다. 그렇다면 계단의 수가 n개일 때는 경우의 수가 몇가지 존재할까? 답이 커질 수 있으므로 답을 1,000,000,007로 나눈 나머지를 출력한다. 입력 입력의 첫 줄은 계단의 갯수 (1 N; A a = ArrayN(N); cout

티스토리툴바