문제2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?입력첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다. 따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.출력2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라. 빗물이 전혀 고이지 않을 경우 0을 출력하여라.예제 입력4 43 0 1 4예제 출력5해결 방법물이 고일 수 있는 위치는 0번째 위치와 n-1번째 위치를 ..

문제N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다. 1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다. 2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다. 3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다. 4. 지붕의 가장자리는 땅에 닿아야 한다. 5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창..

입력n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.출력첫째 줄에 답을 출력한다.예제 입력 1010 -4 3 1 5 6 -35 12 21 -1예제 출력33해결 방법Number10-43156-351221-1Prefix106910152..

문제사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다. 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과..

문제서로 다른 양의 정수로 이루어진 크기가 N인 집합 A가 주어진다. 영선이는 집합에 새로운 양의 정수를 추가하려고 한다. 이때, 집합에 있는 수를 정렬한 결과에서 인접한 두 수의 공약수가 1을 넘으면 안 된다. 그러기 위해서 수를 최소 몇 개 추가해야하는지 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 집합에 포함되어 있는 수가 주어진다. 주어지는 수는 100,000보다 작거나 같은 자연수이다.출력첫째 줄에 수를 최소 몇 개 추가해야하는지 출력한다.예제 입력42200 42 2184 17예제 출력3힌트예제 1의 경우에 {43, 2195, 2199}를 추가하면 된다.해결 방법정렬된 배열의 연속된 두 수들을 순회하면서 그 사이에 추가해야할 숫자가 있다면 추가해..

문제두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 모든 자연수 N은 1과 자기 자신(N)을 약수로 갖게 된다. 실질적 약수(actual divisor)라는 것이 있다. 자연수 N의 약수들 중에서 1과 자기 자신(N)을 제외한 약수를 실질적 약수라고 한다. 따라서 6의 실질적 약수는 2, 3이며, 13의 실질적 약수는 없다. SOD(Sum Of Divisor)라는 함수를 정의하자. SOD(n)은 정수 n의 모든 실질적 약수의 합을 가리킨다. 따라서 SOD(6) = 5이며, SOD(13) = 0이다. 한편, CSOD(Cumulative SOD)라는 함수도 정의해 볼 수 있다. CSOD(n)은 SOD(1) + SOD(2) + … + SOD(n)이라고 하자. CSOD(..

문제동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇..

문제선주는 자신이 운영하는 N개의 논에 물을 대려고 한다. 물을 대는 방법은 두 가지가 있는데 하나는 직접 논에 우물을 파는 것이고 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다. 각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때 최소의 비용으로 모든 논에 물을 대는 것이 문제이다.입력첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어오는데 이는 i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j(1 ≤ Pi,j ≤ 100,000, Pi,j = Pj,i, Pi,i =..