DY N DY

1019 : 소형기관차제한시간: 1000 ms 메모리제한: 64 MB 해결횟수: 665 회 시도횟수: 1995 회 기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 간다. 기관차가 고장나면 기차를 운행할 수 없게 되므로 최근 철도청은 기관차 고장에 대비하여 몇몇 역에 소형 기관차 3대를 배치하기로 결정하였다. 소형 기관차는 평소에 이용하는 기관차보다 훨신 적은 수의 객차만을 끌 수 있다. 기관차가 고장났을 때 끌고 가던 객차 모두를 소형 기관차 3대가 나누어 끌 수 없기 때문에 소형 기관차들이 어떤 객차들을 끌고 가는 것이 좋을까하는 문제를 고민하다가 다음과 같이 하기로 결장하였다.① 소형 기관차가 최대로 끌 수 있는 객차의 수를 미리 정해 놓고 그보다 많은 수의 객차를 절대로 끌게 하..

LCS 성공문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB208493266142.728%문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.예제 입력 복사ACAYKP CAPCAK 예제 출력 복사4 힌트출처문제를 만든 사람: baekjoon 123456789101112131415161718192021222..

2101 : 연속부분최대곱제한시간: 1000 ms 메모리제한: 32 MB 해결횟수: 740 회 시도횟수: 2489 회 N개의 양의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면, 색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다.결과는 double형의 범위를 넘지 않는다. 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 계산된 최대값을 소수점 이하 넷째 자리에서 반올림하여 소수점 이하 셋째 자리까지 출력한다. [Copy] 8 1.1 0.7 1.3 0.9 1.4 0.8 0.7..

시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수1.5 초512 MB107364 (6%)38문제납세의 의무는 국민의 기본적인 의무이다. 세금은 수입에 비례하여 정해진 규칙에 따라 계산되기 때문에, 규칙에 따라서 정확한 수입을 계산하는 것이 중요하다. 여러분은 새로 가게를 열고, 총 N 일 동안 영업을 하였다. 납세의 의무를 성실하게 수행하기 위하여 매 영업일마다 손익(이익 또는 손해)을 기록하여 세무서에 신고하였다. 세금을 매기는데 기준이 되는 수입은 다음 규칙에 의해서 계산된다."1일부터 N일 사이의 어떤 연속된 기간에 대하여 이 기간 동안 손익의 총합을 구한다. 단, 하루 이상의 기간만 고려한다. 다음, 전체 가능한 모든 기간에 대하여 구한 손익의 총합들 중 K번째로 큰 값이 기준이 된다. 즉..

시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수3.0 초512 MB23940 (17%)26문제N개의 정점과 M개의 간선으로 이루어진 양방향 그래프가 주어진다. 1번 정점에서 N번 정점까지의 K번째 최단경로를 구하여라. 같은 거리로 N번 정점에 도달해도 중간에 이동하는 방법이 다르면 서로 다른 경로로 간주하며 같은 간선을 여러 번 이용할 수도 있다. 만약 1번 정점에서 N번 정점까지의 경로가 존재하지 않으면 -1을 출력한다.입력첫 번째 줄에 정점의 개수 N과 간선의 개수 M, 그리고 K가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 500,000, 1 ≤ K ≤ 10)두 번째 줄부터 M개의 줄에 걸쳐 간선의 정보가 입력된다. 간선의 정보는 x, y, z꼴로 주어지며 x에서 y로 가는데..

1848 : 극장 좌석제한시간: 1000 ms 메모리제한: 0 MB 해결횟수: 381 회 시도횟수: 1023 회 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 써 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다. 그런데 이 극장에는 "고정석 회원"들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮..

자두나무 성공문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB130754138639.630%문제자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나..

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