DY의 세상구경

2574 : 사회망 서비스(SNS)제한시간: 1000 ms 메모리제한: 256 MB 해결횟수: 65 회 시도횟수: 547 회 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 간선은 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다. 친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데..

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개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다...

IOIOI 성공한국어원문문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB99122918229.450%문제N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.P1 IOIP2 IOIOIP3 IOIOIOIPN IOIOI...OI (O가 N개)I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000)출력S에 PN이 몇 군데 포함되어 있는지 출력한다.예제 입력 복사1 13 OOIOIOIOIIOII 예제 출력 복사4..

동전 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알고리즘 분류다이나믹 프로그래..

피보나치 수 3 성공문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB112632925937.700%문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.출력첫째..