DY의 세상구경

행렬 곱셈 순서 성공문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB101244429944.035%문제크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.같은 곱..

1769 : 교차하지 않는 원의 현들의 최대집합제한시간: 1000 ms 메모리제한: 0 MB 해결횟수: 14 회 시도횟수: 62 회 평면상에 있는 원의 둘레에 100개의 점이 일정한 간격으로 시계방향으로 번호가 1, 2, ... 100으로붙여져 있다. 이 점들을 끝점으로 갖는 N개의 선분(원의 현)이 입력으로 주어질 때, 이들중에서 서로 교차하지 않는 것들을 최대한 많이 찾아서 그 개수를 출력하는 프로그램을 작성하라. 단, 1≤N≤50이고, 주어진 각 점은 많아야 한 현의 끝점이 될 수 있다. 첫 번째줄은 주어지는 현의 개수 N이고, 다음의 N줄은 각 현의 양끝점의 번호가 주어진다. 구한 현의 개수를 출력한다. [Copy] 5 97 31 1 45 27 5 11 65 43 72 [Copy] 3 [도움말 접..

동물원 성공문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB2044104384850.267%문제어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.입력첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.출력첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력..

쉬운 계단 수 성공문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB45911532111431.621%문제45656이란 수를 보자.이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)입력첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.예제 입력 복사1 예제 출력 복사9 예제 입력 2 복사2 예제 출력 2 복사17 힌트출처문제를 만든 사람: baekjoon알고리즘 분류다이..

RGB거리 성공문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB73383530254048.997%문제RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다...

동전 2 성공문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB72762245140727.889%문제n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.)입력첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 100,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.출력첫째줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.예제 입력 복사3 15 1 5 12 예제 출력 복사3 힌트출처잘못된 조건을 찾은 사람: apples1309알고리즘 분류다이나믹 프로그래..

커플 만들기 성공문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB81721614527.938%문제여자친구가 없는 남자 n명과 남자친구가 없는 여자 m명을 불러 모아서 이성 친구를 만들어 주기로 하였다. 하지만 아무렇게나 해줄 수는 없고, 최대한 비슷한 성격의 사람들을 짝 지어 주기로 하였다.당신은 뭔가 알 수 없는 방법으로 각 사람의 성격을 수치화 하는데 성공하였다. 따라서 각 사람의 성격은 어떤 정수로 표현된다. 이와 같은 성격의 수치가 주어졌을 때, 우선 최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하려 한다. 남자-여자 커플만 허용된다.입력첫째 줄에 n, m(1≤n, m≤1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주..

동전 1 성공문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초4 MB57902221153937.619%문제n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.)입력첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.출력첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.예제 입력 복사3 10 1 2 5 예제 출력 복사10 힌트알고리즘 분류다이나믹 프로그래밍동전 교환123456789101112131415161718192021222324#includ..