딩신 - 코딩의 신

특정 최단거리 문제그래프가 주어질 때, 정점 1번에서 정점 N번으로 가는 최단거리를 구하려 하는데, 그 과정에서 두 개의 정점을 반드시 거쳐야 한다. 한 번 방문했던 정점을 또 다시 방문하는 것도 허용하고, 간선도 마찬가지로 여러번 방문하는 것을 허용한다고 할 때, 1번에서 N번으로 가는 “특정한" 최단거리를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b, c로 이루어져 있으며, 이는 정점 a와 정점 b가 가중치 c인 간선으로 연결되어 있다는 의미이다. 마지막 줄에는 반드시 거쳐야 하는 두 정점 A, B가 주어진다. 출력1번 정..

파티 문제철수네 마을에는 N개의 집이 있으며, 각 집은 고유한 번호를 부여받는다. 각 번호는 1보다 크거나 같고, N보다 작거나 같다. 철수는 마을 K에 살고 있다. 집과 집 사이에는 단방향 도로가 존재하기 때문에, 이 도로를 통하여 서로 이동할 수 있다. 즉, N개의 마을은 그래프 구조를 이룬다. 편의상 각 집에는 한 사람만이 살고 있다고 가정하자. 크리스마스인 오늘, 철수는 본인의 집에서 파티를 열려고 한다. 따라서 다른 모든 사람들이 철수의 집에 모여 파티를 즐기고, 파티가 끝난 후에는 다시 본인의 집으로 돌아가려 한다. 사람들은 본인의 집에서 철수네 집까지 이동하기 위하여 항상 최단거리로 이동하기를 원하고, 마찬가지로 철수네 집에서 본인의 집에 갈 때도 최단거리로 이동하기를 원한다. 집의 개수와 ..

최단거리 문제그래프와 출발점, 도착점이 주어질 때 출발점에서 도착점까지 이동하기 위한 최단거리를 출력하는 프로그램을 작성하시오. 예를 들어, 아래 그림에서 출발 정점이 0, 도착 정점이 10이라고 할 때, 최단거리는 3이다. 입력첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 10,000, 1 ≤ M ≤ 1,000,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a와 정점 b가 연결되어 있다는 의미이다. M+1 번째 줄에 대하여 출발점과 도착점의 정점 번호가 주어진다. 출력출발점에서 도착점까지 이동하기 위한 최단거리를 출력한다. 예제 입력11 14 0 1 0 2 1 2 1 4 1 5 2 3 3 7 4 7 4 9 4 ..

문제N명의 학생을 M개의 팀으로 나누려고 한다. 각 학생은 본인의 능력을 나타내는 숫자를 하나씩 갖고 있으며, 편의상 팀을 나눌 때에는 연속한 학생들을 하나의 팀으로 만든다고 하자. 예를 들어, 다음 그림은 10명의 학생을 3개의 팀으로 나누는 두 가지 예이다.각 팀의 점수는 그 팀에 속한 학생들의 점수의 합이다. 예를 들어, 첫 번째의 경우 각 팀의 점수는 9/7/14 가 되며, 두 번째의 경우에는 4/16/10 이 된다. 팀을 잘 나누기 위해서는, 각 팀의 점수가 비슷해야 한다. 즉, 하나의 팀의 점수가 매우 높아서는 안 된다. 따라서 점수가 최대인 팀의 점수를 최대한 적게 만들고 싶다. 위의 예제에서는 아래와 같이 나누게 되면, 각 팀의 점수가 9/11/10 이 된다. 점수가 최대인 팀은 11이며,..

연속부분 최대합 L 문제N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다. 입력첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 1,000,000 ) 두 번째 줄에 n개의 정수가 주어진다. 출력연속된 부분을 선택하였을 때의 최댓값을 출력한다. 예제 입력8 2 3 -5 8 -3 4 2 -9예제 출력11 예제 입력5 -1 -2 3 -2 4예제 출력5 코드///연속부분의 최대합 import java.util.*; public class Main { public static ArrayList box = new ArrayList(); public static int re..

자원채취 문제N x M의 지도가 주어지며, 이 지도의 각 칸에는 자원이 존재한다. 자원의 양은 정수로 나타난다. 다음 그림은 5 x 6 의 지도에 존재하는 자원을 나타낸다.철수는 자원을 채취하는 로봇을 갖고 있으며, 이 로봇은 (0, 0) 에서 출발하여 (N-1, M-1) 에서 자원 채취를 마친다. 로봇은 한가지 제약이 있는데, 오른쪽과 아랫쪽으로밖에 움직일 수 없다는 것이다. 이 로봇을 이용하여 가장 많이 채취할 수 있는 자원의 양을 출력하는 프로그램을 작성하시오. 위의 예제의 경우 다음과 같이 채취하는 것이 최대이며, 그 양은 49이다. 입력첫 번째 줄에 N, M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 두 번째 줄부터 N x M 의 지도에 존재하는 자원의 양이 주어진다. 출력로봇을 이용하여..

제곱수의 합 문제숫자 N을 제곱수의 합으로 표현하고자 할 때, 사용해야 하는 제곱 수의 최소 개수를 출력하는 프로그램을 작성하시오. 예를 들어, 숫자 45를 제곱수의 합으로 표현하고자 할 때 필요한 제곱 수의 최소 개수는 2개이며, 이는 다음과 같다.45 = 3^2 + 6^2 입력첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 출력필요한 제곱 수의 최소 개수를 출력한다. 예제 입력45예제 출력2 예제 입력38예제 출력3 코드///제곱수의 합 // greedy 하게 찾고 , 다시 찾기, 100점 import java.util.*; public class Main { public static ArrayList box = new ArrayList(); public static int resu..

직사각형 배치의 경우의 수 문제2 x N 직사각형 모양의 칸이 있다. 이를 2 x 1 모양의 타일로 가득 채우려 한다. 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 단, 가능한 경우의 수가 매우 많을 수 있으므로, 그 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.예를 들어, N = 3 일 경우에는 다음 세 가지의 가능한 경우가 존재한다. 입력첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100 ) 출력가능한 경우의 수를 1,000,007 로 나눈 나머지를 출력한다. 예제 입력3예제 출력3 예제 입력8예제 출력34 예제 입력37예제 출력87896 코드///사각형 import java.util.*; public class Main { // public static ArrayList bo..

구슬 게임 문제철수와 영희는 구슬 게임이 구슬 게임을 하려 한다. 이 구슬 게임의 규칙은 다음과 같다.철수와 영희는 번갈아가며 구슬을 가져간다. 맨 처음에는 철수가 구슬을 가져간다.구슬을 가져갈 때에는, 최소 1개에서 최대 3개까지 구슬을 가져갈 수 있다.가져갈 구슬이 없는 사람이 진다.예를 들어 5개의 구슬이 있다고 하자. 여기서 철수가 1개의 구슬을 가져가고, 영희가 3개의 구슬을 가져간 후, 철수가 마지막으로 1개의 구슬을 가져갔다고 가정하면 이 게임의 승자는 철수가 된다. 물론, 각자가 어떻게 구슬을 가져가느냐에 따라 승패가 달라질 수 있다. 철수와 영희는 이기기 위해서 최선을 다해서 게임을 플레이 한다. n개의 구슬을 시작으로 게임을 진행한다고 할 때, 철수가 이 게임을 이길 수 있다면 YES,..

직사각형의 합 문제N(Row) x M(Col) 의 직사각형이 주어지며, 각 칸에는 정수가 들어있다. 이제 Q개의 질문에 대하여 답을 해야 하며, 각각의 질문은 (a, b)부터 (c, d)까지의 직사각형에 들어있는 정수의 합을 묻는다. 예를 들어, 다음과 같이 5 x 5 의 직사각형이 주어질 때, (1, 2) 부터 (3, 3) 까지의 직사각형에 들어있는 정수의 합은 26 이다. 입력첫 번째 줄에 N, M, Q가 주어진다. ( 1 ≤ N, M ≤ 1,000, 1 ≤ Q ≤ 1,000,000 ) 두 번째 줄부터 N x M 직사각형에 주어진다. 그 후 Q개의 질문이 주어진다. 각각의 질문은 “a b c d” 로 이루어 져 있으며, 이는 (a, b) 부터 (c, d) 까지의 직사각형에 들어있는 정수의 합을 묻는다..