12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 과정 처음에는 DP : 자신을 포함하는 물건들의 최대 가치 를 담는 용도였다. #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N = 0; // 물건의 수 int K = 0; // 최대 무게 int W = 0; // 물건의 무게 i..

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 과정 x2-x1, y2-y1 범위에 들어있는 숫자를 for문으로 더할까 하다가 그럼 시간초과가 날 것 같아서 애초에 숫자를 받을 때, 같은 열!!!!! 기준으로 누적값을 벡터에 저장한 후, 범위를 받아서 최대좌표의 누적값 - 최소 좌표의 누적값 을 했다. 이 문제를 풀 때 가장 시간이 오래걸린 점은 바로 행렬을 개같이 못했다는 점이다. 행 = Row = x값 = 가로 열 = Column = y값 = 세로 코드 #inclu..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 과정 맨 처음 문제를 보고 너무 쉽다고 생각했다. 그냥 수열 받을 때 마다 최대값 저장해서 비교하면 되는거 아닌가? 해서 나온 코드.. #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N = 0; // 수열의 크기 ve..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 과정 음.. 그니까 내집 기준 앞번호, 뒷번호랑 집의 색까리 같으면 안된다. 그리고 색칠하는 비용이 모두 다르고, 최소값을 구하라고 하니까, DP와 min을 사용해서 코드를 짜볼것이다. 고민을 가장 많이 한 부분은 단순 최소값만 생각할게 아니라, 색의 종류도 함께 고민을 해야한다는 점이었다. key:value로 넣을 것인지, 아니면 그냥 RGB순서로 인덱스로 구분할 것인지 고민했다. : 이 부분은 코드를 짜다보니, 어차피 DP라는 특성상 현..

2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 과정 처음에는 그래프인가 했다가 이것도 계단 오르는 규칙이 있는 문제이므로 DP를 이용해서 풀어보려고 했다. 계단을 오르는데는 2가지 규칙이 있다. 1. 연속된 2개 계단 오르기 2. 한 칸만 건너뛰기 즉, 현재 내가 서있는 칸(N)을 연속된 2번째 계단으로 만들건지,(N-1을 밟은 상태) 한칸 건너뛴 계단으로 만들건지(N-1을 안밟은 상태) 결정해야 한다. 따라서, DP[N] = max(DP[N-3] + Arr[N-1] + Arr[N], DP[N-2] + Arr[N]) 또..