DP

https://www.acmicpc.net/problem/5681시간 제한메모리 제한1초128MB문제KDK방송국은 새로운 게임 쇼를 하나 만들었다. 참가자는 선택을 몇 개 하게 되고, 이 선택에 따라서 상품을 얻게 된다. 먼저, 공이 삼각형 모양으로 쌓여져 있고, 각 공에는 정수 값이 하나씩 쓰여 있다. 아래 그림은 한 예이다.참가자는 공을 고를 수 있고, 고른 공에 쓰여 있는 숫자의 합이 점수가 된다. 공을 고르면, 그 공은 삼각형에서 제거된다. 점수가 높을수록 좋은 상품을 받게 된다. 하지만, 참가자는 그 공의 위에 있는 공을 고른 경우에만 그 공을 고를 수 있다. 또, 참가자는 공을 고를 것인지, 게임을 중단할 것인지 선택할 수 있다. 만약, 공을 하나도 고르지 않은 경우에 점수는 0이 된다. 프로..

https://www.acmicpc.net/problem/25589시간 제한메모리 제한1초1024MB문제N*N 크기의 격자 위에 칸마다 코인이 놓여있다.푸앙이는 격자 위에 한 변의 길이가 1 이상 N이하인 정사각형 그물을 만들어 그 안의 코인을 얻을 수 있다. 하지만 그물이 포함하는 칸 개수의 제곱에 해당하는 코인을 지불해야 한다.그물은 반드시 N*N크기의 격자 안에 완전히 포함 되어야 하고, 한 번 그물을 친 칸에는 다시 그물을 칠 수 없다.푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 구하시오. 입력첫 번째 줄에 정수 N(2 ≤ N ≤ 400)이 주어진다.두 번째 줄부터 N개의 줄에는 칸에 놓여 있는 코인의 수가 1행부터 차례대로 주어진다. 칸에 놓여 있는 코인의 수는 10^..

시간 제한메모리 제한2초1024MB문제에릭은 방학 동안 너무 심심한 나머지, 당근 클릭 게임이라는 게임을 직접 만들어서 플레이하기로 했다. 이 게임에서 초기에 에릭은 당근을 0개 가지고 있고, s가 1인 상태로 게임을 시작한다.그 후, 매초 다음 두 가지의 행동 중 하나를 할 수 있다.마우스를 클릭하고 당근을 s개 얻는다.정수 i (1 ≤ i ≤ N)를 고르고, 당근 Ai개를 지불하여 i번째 스피드 효과를 구매한다. 구매 직후, s가 Bi만큼 증가한다. (이전에 구매한 스피드 효과를 다시 구매하는 것도 가능하다.)게임을 개발하느라 에너지를 모두 소모해 버린 에릭을 위해 게임을 K초 플레이한 후 당근을 최대 몇 개까지 가지고 있을 수 있는지 알려주자!입력첫 번째 줄에 두 정수 N, K가 공백으로 구분되어 ..

시간 제한메모리 제한1초128MB문제어떤 도시의 중심가는 N개의 동서방향 도로와 N개의 남북방향 도로로 구성되어 있다. 모든 도로에는 도로 번호가 있으며 남북방향 도로는 왼쪽부터 1에서 시작하여 N까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 N까지 번호가 할당되어 있다. 또한 동서방향 도로 사이의 거리와 남 북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 (동서방향 도로 번호, 남북방향 도로 번호)로 나타낸다. N이 6인 경우의 예를 들면 다음과 같다.이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1, 1)의 위치에 있고 경찰차2는 (N, N)의 위치에 ..

n크기의 배열 arr이 주어지고 k번째 항목까지의 합을 구하는 코드는 아래와 같이 간단히 구현할 수 있다. sum = 0 for i in range(1, k+1): sum += arr[i] print(sum) i번째 항목까지의 합을 구하는 코드는 1부터 k번째까지의 항목을 탐색하며 한 번씩 합 연산을 실시하므로 시간 복잡도가 O(N)이다. 나쁘지 않은데? 그런데 배열 길이가 106, 테스트 케이스가 103개가 된다면 어떨까. 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicp..

시간 제한 메모리 제한 1초 128MB 문제 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, (생략)과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해..

시간 제한 메모리 제한 1초 (추가 시간 없음) 512MB 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태(생략)이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래(생략)와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, ..

시간 제한 메모리 제한 2초 128MB 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림(생략)과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로(생략)가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는..