문제 링크: https://www.acmicpc.net/problem/10986 문제수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) 출력첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.풀이접근법어떠한 구간에 대해서 M으로 나누어 떨어져야 한다면, 처음 ~ 시작, 처음 ~ 끝에 대한 누적합에..

문제 링크: https://www.acmicpc.net/problem/3151 문제Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. 코딩 실력이 좋으면 팀워크가 떨어지고, 팀워크가 좋을수록 코딩 실력이 떨어진다. 그리고 출전하고자 하는 대회는 코딩 실력과 팀워크 모두가 중요하다.Elly는 그녀가 가르칠 수 있는 모든 학생들의 코딩 실력을 알고 있다. 각각의 코딩 실력 Ai는 -10000부터 10000 사이의 정수로 표시되어 있다. 그녀는 팀워크와 코딩 실력이 모두 적절한 팀을 만들기 위해, 세 팀원의 코딩 실력의 합이 0이 되는 팀을 만들고자 한다. 이러한 조건 하..

문제 링크: https://www.acmicpc.net/problem/31501 문제이 문제는 DP (Large)와 문제의 수 제한, 질문의 수 제한, 문제의 난이도 제한이 다른 문제이다.DP는 DYNAMIC Porani의 약자이다.DYNAMIC한 포라니는 가능한 문제를 DYNAMIC하게 푸는 것을 좋아한다. DYNAMIC한 문제 풀이란 문제의 번호와 난이도가 모두 증가하도록 가능한 한 많이 푸는 것이다.방학을 맞은 포라니는 알고리즘 능력 향상을 위해 선배로부터 추천 문제 셋을 받았다. 나태한 포라니는 모든 문제를 풀고 싶지 않다. 만약 선배로부터 어떤 문제를 풀라는 지시를 받았을 때, 그 문제를 포함하여 DYNAMIC하게 문제를 풀었을 경우 몇 문제를 풀어야 하는지 알려주자. 입력첫 번째 줄에 문제의 ..

문제 링크: https://www.acmicpc.net/problem/6574 문제상근이는 두 과일의 유전자를 합쳐, 새로운 과일을 만드는 작업을 하고 있다. 두 과일을 합치는 작업은 매우 어렵다. 만약, 성공을 하게 된다면 새로운 과일의 맛은 두 과일을 동시에 먹는 맛과 같을 것이다.사실 상근이는 이 작업을 시작하기 전에, 새로운 과일의 이름을 짓고 작업을 시작 한다. 물론, 사과(apple)와 배(pear)를 합친 과일을 apple-pear라고 불러도 되지만, 이 이름은 관심을 끌기에 적절하지 않는다.상근이는 두 과일의 이름을 부분 문자열로 포함하는 문자열 중, 가장 길이가 짧은 것을 새로운 과일의 이름으로 사용하려고 한다. 예를 들어, applear는 apple과 pear를 모두 포함한다. (APP..

문제 링크: https://www.acmicpc.net/problem/17490 문제학교의 홍보대사를 맡게 된 건덕이는 건국대학교의 모든 강의동을 신입생들에게 소개해야 한다.건국대학교 중앙에 위치한 일감호를 따라 한 바퀴를 돌며 모든 강의동을 소개하는 것이 그의 일이지만, 몇몇 구간들이 공사 중이어서 그 구간을 통해서는 갈 수 없는 상황이다. 급한대로 건덕이는 호수에 돌을 던져 징검다리를 놓아 길을 만들어보려고 한다.강의동은 일감호의 둘레에 따라 원형으로 배치돼 있으며, 강의동 양 옆의 강의동은 서로 이웃한다. 또, 원형으로 배치돼 있기 때문에 N개의 강의동이 있다면 N번째 강의동과 1번째 강의동은 서로 이웃한다.일감호 안에는 와우도라는 섬이 있다. 건덕이는 한 강의실에서 다른 모든 강의실로 이동할 수 ..

문제 링크: https://www.acmicpc.net/problem/14461 문제소가 길을 건너는 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.존의 농장에는 작은 정사각형 목초지가 N×N (3 ≤ N ≤ 100) 격자로 이루어져 있다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다. 이 농장에 사는 소 베시는 한 목초지에서 상하좌우로 인접한 다른 목초지로 이동할 수 있지만, 교통사고를 피하기 위해 차가 안 오는지 확인하고 길을 건너야 한다. 길을 건너는데는 T초 (0 ≤ T ≤ 1,000,000)가 걸린다.존이 베시에게 체스 대결을 신청했다. 베시는 북서쪽 끝에 있는 목초지에서 남동쪽 끝에 있는 존의 집으로 가..

문제 링크: https://www.acmicpc.net/problem/17090 문제크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다.어떤 칸(r, c)에 적힌 문자가U인 경우에는 (r-1, c)로 이동해야 한다.R인 경우에는 (r, c+1)로 이동해야 한다.D인 경우에는 (r+1, c)로 이동해야 한다.L인 경우에는 (r, c-1)로 이동해야 한다.미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다. 입력첫째 줄에 미로의 크기 N, M(3 ≤ N, M ≤ 500)이 ..

문제 링크: https://www.acmicpc.net/problem/22953 문제도도는 주방장이다. 총 K개의 요리가 준비되는 최소 시간을 구해야 한다.각각의 요리사는 자신만의 음식 조리 시간이 있다. 음식 조리 시간은 음식 하나를 만들 때 걸리는 시간이다.도도는 요리사에게 격려를 해줄 수 있다. 격려받은 요리사는 영구적으로 음식 조리 시간이 1초 감소한다.도도는 한 요리사에게 여러 번 격려할 수 있고, 요리사의 음식 조리 시간을 1초 미만으로 줄일 수는 없다.도도를 위해 요리에 걸리는 최소 시간을 출력하는 프로그램을 만들어 보자. 입력첫째 줄에 요리사의 수 N (1 ≤ N ≤ 10), 만들어야 할 음식의 개수 K (1 ≤ K ≤ 1000000), 격려해줄 수 있는 횟수 C (1 ≤ C ≤ 5)가 주..

문제 링크: https://www.acmicpc.net/problem/26009 문제통학러 재헌이는 1교시 수업을 듣기 위해 아침 일찍 학교에 가려고 한다. 재헌이가 사는 지역은 크기가 N x M 인 격자로 나타낼 수 있는데, i행 j열에 해당하는 칸을 (i, j) 로 나타낼 때 재헌이는 현재 (1, 1)에, 학교는 (N, M)에 위치해 있다. 재헌이는 상하좌우로 한 칸씩 이동할 수 있고 지역 바깥으로 나갈 수는 없다.등굣길은 순탄치만은 않은데, 이 지역에는 K개의 정체 구역이 있다. 𝑖$i$번째 정체 구역은 세 정수 Ri, Ci, Di로 표현되며, 이는 (Ri, Ci)로부터 거리가 Di 이하인 칸들에는 극심한 교통 정체가 일어나고 있음을 의미한다. 두 칸 (R1, C1), (R2, C2) 사이의 거리..