asdf11111111111111111111

기초적인 미적분 지식이 있다면, 가속도는 속도-시간 그래프로 이해하면 편하다.

다들 교과서 등에서 $$v^2 - v_0^2=2as$$와 같은 공식들을 외웠을 것이다.

그러나 나는 이런 공식들은 사용하지 않을 생각이다.

그런데도 그 공식들을 자연스럽게 유도할 수 있을 정도로 한 차원 높은 방식으로 이해할 것이다.

이전 글에서 우리는 s = vt, v = at 두 공식을 이해했다.

이번 글에서 다루는 내용만 잘 이해한다면 사실 단순고전역학 문제는 속도-시간 그래프 하나로 모조리 풀어버릴 수 있다.

v=at를 미분해보면

$$\frac{dv}{dt}=a$$

이므로 속도를 미분하면 가속도이고,

v=at를 적분해보자면

$$\int_{}^{} v dt = \frac{1}{2}at^2 + C $$

여기서 v=at이므로

$$\int_{}^{} v dt = \frac{1}{2}vt + C $$

s=vt이므로

$$\int_{}^{} v dt = \frac{1}{2}s + C $$

1/2이 있긴 하지만 일단 무시하고 보면, 속도를 적분하면 변위가 나온다.

따라서 다음과 같다.

속도-시간 그래프는 다음과 같이 그릴 수 있다.

위와 같은 그래프를 공식으로 표현하면 어떨까?

$$y=mx\ (m은\ 기울기)$$ 라고 했을 때, y축이 속도 (v), x축이 시간 (t), 기울기가 가속도 (a)이므로 다음과 같이 표현할 수 있다.

$$v=at$$

속도-시간 그래프는 위에서 본 그 식의 그래프인 것이다.

그래프의 넓이는 적분이고 기울기는 미분이므로

이 그래프의 기울기와 넓이를 따져보면 가속도와 변위를 전부 구할 수 있다.

단위를 한번 따져보자.

변위를 구하기 위해서 세로축과 가로축을 곱하면 $$\frac{m}{s} \times s = m$$

가속도를 구하기 위해 세로축에 가로축을 나누면 $$\frac{m/ s}{ s} = m/s^2$$

단위들도 쫙 쫙 맞아떨어진다.

예시를 한번 보도록 하자.

ex) 물체가 10 (m/s) 에서 속력이 일정한 가속도로 감소하여 2초 이후 정지한 경우

일정한 가속도 = 일정한 기울기 = 기울기가 같다

정지 = 속력이 0

따라서 속도-시간 그래프를 다음과 같이 그릴 수 있다.

이때 변위(넓이)는? $$10 (m/s) * 2 (s )/ 2 = 10 (m)$$

가속도(기울기)는? $$(0-10) (m/s) / 2 (s)= -5 (m/s^2)$$

그럼 이 물체는 멈추기까지 10m를 이동했고, 가속도는 -5m/s^2 였음을 알 수 있다.

가속도가 0일 경우는 어떻게 될까?

가속도 = 기울기 이므로 기울기가 0인 x축에 평행한 직선이 그려질 것이고, 속도의 변화는 없을 것이다.

물체가 멈추는게 아니라 물체가 등속도로 이동하게 될 것이다.

물체에 '힘'을 주면 속도가 변하는 것처럼 보인다.

그러나 뉴턴이 잘 관찰해본 결과, 속도가 변하는 것이 아니라 가속도가 변한다.

그리고 이를 정리한 것이 뉴턴 제 2법칙이다.

$$ F=ma $$

가속도가 변해서 속도도 변하는 것일 뿐이다.

잠깐 벡터와 스칼라를 간단하게 설명하자면, 벡터는 방향이 있는 물리량, 스칼라는 방향이 없는 물리량이다.

가속도는 대표적인 벡터이고, 질량은 대표적인 스칼라이다.

그리고 벡터는 정수배하여 방향은 그대로 유지하면서 (또는 정반대로 바꾸면서) 크기를 늘리거나 줄일 수 있다.

F=ma도 똑같다. a는 벡터고 m은 스칼라이므로 F는 a라는 벡터를 m만큼 정수배한 벡터인 것이다.

보통은 알짜힘 (F)이 주어지면 질량 (m)으로 나누어 물체의 가속도 (a)를 얻는다.

이 순서의 대표적인 예외는 중력인데, 중력은 모든 물체가 같은 힘 (F)이 아니라 같은 가속도 (a)를 갖도록 만든다.

그래서 중력은 a (= g = 9.8)에 질량(m)을 곱해서 중력 (F)을 얻는다.

ex) 자유 낙하하고 있는 5kg 물체를 중력과 반대 방향으로 5N 당길 때, 이 물체의 가속도의 크기는?

중력부터 위의 서술된 순서로 구해보면, F = 5 * 9.8 = 49 (N)

중력과 반대로 작용하는 힘만큼 빼보면 알짜힘은 아래 방향으로 49-5 = 44 (N)이다.

그럼 가속도는? F = ma에서 F에 44, m에 5를 대입하면 a = 8.8 (방향은 알짜힘과 같은 아래 방향!)

물리는 물(物)체에 담긴 이(理)치를 연구하는 학문이다.

물체는 움직이거나 움직이지 않거나 의 이분법으로 나눌 수 있다.

움직이지 않는 물체는 따로 표현할 방법을 찾지 않아도 괜찮아 보인다.

그렇다면 움직이는 물체의 운동은 어떻게 기술하면 좋을까?

물리에서는 운동을 기술하기 위한 기준을 '시간'으로 잡았다.

따라서 우리는 어떤 물체의 운동을 '2초에 북쪽으로 4m 움직였다' 와 같이 분석하게 되었다.

여기서 '북쪽으로 4m'가 변위, '2초'가 시간임을 알 수 있다.

근데 여러 물체를 관측하다 보니, A도 '2초에 북쪽으로 4m' 움직였고, A 기준으로 남쪽 8m 뒤에 있던 B도 '2초에 북쪽으로 4m' 움직였다.

둘 사이의 뭔가 공통점이 있는 것 같은데... 이를 어떻게 표현할까?

이를 표현하기 위해 '속도'라는 개념이 도입됐다.

속도란 일정 시간동안 이동한 거리 (+방향)이다.

운동을 설명하는 기준은 시간이므로, "같은 시간이 흘렀다고 쳤을 때" 움직인 거리를 파악하는 것이다. 따라서

$$속도 = 거리 / 시간$$

$$ v = s / t $$

v= velocity

s= spatium

t = time

A와 B는 둘 다 같은 시간 동안 같은 방향으로 같은 거리를 갔으므로, 같은 속도로 운동한다고 할 수 있다.

그리고 2초에 8m를 가나, 3초에 12m를 가나 모두 같은 속도임을 알 수 있다.

(같은 1초가 흘렀다고 치면 둘 다 4m를 이동할 것이므로)

$$ 8/2 = 12/ 3 = 4 $$

어떤 운동의 속도까지 분석했다고 치자. 그런데 만약 그 물체의 속도가 변한다면 그 변화는 어떻게 표현해야 할까?

우리는 변위가 변했을 때, 이를 비율화하여 속도를 얻을 수 있었다.

그렇다면 속도가 변했을 때, 이것 또한 비율화할 수 있을 것이며, 이를 가속도라고 한다.

앗! 갑자기 뇌정지가 오는 이유가 뭘까?

속도까지는 직관적인데, 가속도는 그렇지 않기 때문이다!

그렇다면 속도까지만 보면 되지 왜 이런 비직관적인 가속도까지 구하는 걸까?

그 이유는 물체에 힘을 줬을 때 변하는 것은 속도가 아니라 가속도이기 때문이다.

필자는 고등학생 때 물리 2를 했다. (2009년 개정 교육과정)

당시 내가 다니던 학교에는 놀랍게도 물리 2 수업이 개설되어 있었지만, 실상은 물리 1 보충시간의 개념으로 운영됐다.

나는 '어려운 물리 2를 한다'는 자부심과 더불어 물리 2만의 오묘한 재미를 느껴 물리 2를 끝까지 놓지 못했다...

결국 이래저래 독학해서 20년도 수능에서 48점으로 무려 "2등급"을 달성하고 만다...

아무튼 수능은 운빨이니깐....... 독학하는 과정에서 물리의 정수를 나름 깨달았고 그 증거로

대학 1학년 때 들은 물리 과목에서는 중간 기말 전부 만점,

물리학 실험 과목에서는 압도적으로 1등을 달성하고 A+를 받을 수 있었다.

고딩 때 3년 삽질한 노력이 어디가지 않은 것 같았다.

성적은 인증해줄 수도 있지만은 어짜피 엑셀파일이고 사진파일이기 때문에 충분히 조작이 가능하다고 생각하여 딱히 올리지는 않겠다.

아무튼 내가 아는 수준은 딱 2009년 개정 교육과정 고등학교 물리2, 대학물리학 (교양) 정도다.

그러니까 이후 연재될 내용은 심화적인 물리가 아니라 일회용성 교양 물리 공략인 것이다!

내 주변에도 대학에서 교양 물리를 강요하는데 따라오지 못하고 답답해하는 사람들을 많이 봤다.

그런 사람들을 위해 이 공략 "실전 압축" 물리, 실압물을 바친다!

물리학 책에 있는 잡다한 내용들은 쏙 빼고, 스스로 문제를 이해하고 해결하는 데 도움이 되는 내용만 최대한 담도록 하겠다.

이왕 3학점짜리 강의 듣는거 이 공략으로 핵심을 이해해서 기분좋게 A+ 받기를 바란다.

https://www.acmicpc.net/problem/16917

2초 / 512MB

문제

현진 치킨에서 판매하는 치킨은 양념 치킨, 후라이드 치킨, 반반 치킨으로 총 세 종류이다. 반반 치킨은 절반은 양념 치킨, 절반은 후라이드 치킨으로 이루어져있다. 양념 치킨 한 마리의 가격은 A원, 후라이드 치킨 한 마리의 가격은 B원, 반반 치킨 한 마리의 가격은 C원이다.

상도는 오늘 파티를 위해 양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하려고 한다. 반반 치킨을 두 마리 구입해 양념 치킨 하나와 후라이드 치킨 하나를 만드는 방법도 가능하다. 상도가 치킨을 구매하는 금액의 최솟값을 구해보자.

입력

첫째 줄에 다섯 정수 A, B, C, X, Y가 주어진다.

출력

양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하는 비용의 최솟값을 출력한다.

제한

• 1 ≤ A, B, C ≤ 5,000
• 1 ≤ X, Y ≤ 100,000

• 반반 치킨을 두 마리 구입해 양념 치킨 하나와 후라이드 치킨 하나를 만드는 방법도 가능
• 양념 치킨 한 마리의 가격은 A원, 후라이드 치킨 한 마리의 가격은 B원, 반반 치킨 한 마리의 가격은 C원
• 다섯 정수 A, B, C, X, Y
• 1 ≤ A, B, C ≤ 5,000
• 1 ≤ X, Y ≤ 100,000
• 양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하는 비용의 최솟값

풀이 (C++)

• iostream
• algorithm
• 브루트 포스

풀이 과정

문제의 핵심은 반반치킨

반반치킨은 두 개 단위로 구매할 수 있고, 반반치킨 두 개 = 양념치킨 하나 + 후라이드치킨 하나

치킨을 딱 맞게 구매할 필요 없이 최소 X마리, Y마리 구매하면 되므로 가격만 싸다면 개수가 넘어도 된다

반반치킨의 개수를 0개부터 시작하여 X, Y 중 더 큰 값까지 살펴본다

최악의 경우가 100000 ( 0이 5개 )이므로 충분히 2초 내에 가능 ( 브루트 포스의 근거 )

다음은 x=3이고 y=2일 때 오로지 개수만 따진 표이다

다음과 같은 4가지 경우의 수가 나오며, 모든 경우의 수에 대해 최소 가격을 찾아주면 된다

제일 오른쪽 줄은 반반치킨으로 만든 양념/후라이드의 갯수를 칭한다

초록색 네모와 같이 음수가 나올 수 있다 ( 사야 할 개수가 음수라는 뜻이므로 1개가 남는다는 뜻 )

그러나 위에서 살펴봤듯 치킨은 남을 수 있으니 가격을 계산할 때는 음수는 0으로 취급한다

남을 수 있다고 해서 x, y보다 더 사는 경우는 무조건 최솟값보다 더 사게 되므로 x, y 중 큰 수까지만 고려해준다

( 목표는 몇 개를 사던지 간에 최소 x, y 개를 사기만 하면 되는데, 그 중 최소 가격을 찾는 것이기 때문 )

1. 7번 줄 // 수 입력 순서 주의
2. 9번 줄 // 어짜피 반반치킨은 두 개 단위로 구매해야 하므로 값을 두배시켜 준다
3. 10~17번 줄 // ban은 반반치킨의 갯수( 의 1/2개 ) , x, y중 더 큰 값까지 살펴본다
   1. 11~12번 줄 // 양념 후라이드 단일 구매 갯수에서 반반치킨에 의해 감소되는 양 계산
   2. 13~14번 줄 // 만약 음수라면 ( 그만큼의 치킨이 남는다면 ) 0으로 처리
   3. 15번 줄 // 가격 계산
   4. 16번 줄 // 정답 비교, 초기화를 -1로 해두어서 대소비교가 적절히 이루어지도록 한다 ( 0으로 해두면 0이 계속 최솟값일 것이므로, 그런데 a,b,c 모두 최솟값이 1이라 가격이 0인 경우는 없긴 하다 )
4. 18번 줄 // 정답 출력

주의사항

1. 정답이 int 범위를 넘을 수 있다 ( 곱하기 형변환 주의 / int 끼리 곱한다고 long long 안된다==> 이 코드에서는 변수부터 long long으로 선언해서 해결 )
2. 주어진 치킨의 개수는 '최소'임 ( 치킨이 남을 수 있음 )
3. 정답 비교할 때 가능한 경우의 최솟값보다 작은 수 또는 최대값 보다 큰 수로 초기화 해둬야 한다

https://www.acmicpc.net/problem/16968

1초 / 512MB

문제

상도시의 차량 번호판 형식이 주어졌을 때, 가능한 차량 번호판의 개수를 구해보자.

• 번호판에 사용할 수 있는 숫자는 0, 1, 2, ..., 8, 9이다.
• 사용할 수 있는 문자는 a, b, c, d, ..., y, z이다.
• 차량 번호판의 형식은 최대 4글자이고, c와 d로 이루어진 문자열로 나타낼 수 있다.
• c는 문자가 위치하는 자리, d는 숫자가 위치하는 자리이다.
• 같은 문자 또는 숫자가 연속해서 2번 나타나면 안 된다.

예를 들어, 형식이 "cd"이면, a1, d4, h5, k4 등이 가능하다. 형식이 "dd"인 경우에 01, 10, 34, 69는 가능하지만, 00, 11, 55, 66은 같은 숫자가 2번 연속해서 불가능하다.

입력

첫째 줄에 차량 번호판의 형식이 주어진다. 형식은 길이가 4보다 작거나 같으며, c와 d로만 이루어져 있다.

출력

첫째 줄에 가능한 차량 번호판의 개수를 출력한다.

• 0, 1, 2, ..., 8, 9
• a, b, c, d, ..., y, z
• 최대 4글자
• c는 문자가 위치하는 자리, d는 숫자가 위치하는 자리
• 같은 문자 또는 숫자가 연속해서 2번 나타나면 안 된다
• 가능한 차량 번호판의 개수

풀이 (C++)

• iostream
• string

풀이 과정

연속으로만 나오면 안 된다 그리고 경우의 수만 구하면 된다

처음 가능한 '숫자'의 경우의 수는 10, 이후 반복 출현할 경우 9 // ex) dddd => 10*9*9*9

처음 가능한 '글자'의 경우의 수는 26, 이후 반복 출현할 경우 25 // ex) cccc => 26*25*25*25

따라서 '숫자'일 경우에는 '글자'의 경우의 수를 26으로 복구해줘야하고

'글자'의 경우에는 '숫자'의 경우의 수를 10으로 복구해줘야 한다

( 같은 종류가 연속되는 경우가 아니므로 )

ex) cdcd => 26*10*26*10

1. 8번 줄 // 입력 받음
2. 11번 줄 // 정답은 1로 준비 ( 최대 경우의 수 26*25*25*25가 int 범위 내이므로 int로도 가능 )
3. 13~22번 줄 // 한 글자씩 확인한다
   1. 13~17번 줄 // 만약 d일 경우
   2. 정답에 가능한 숫자 경우의 수 곱함
   3. c는 26으로 초기화
   4. 수가 연속될 것에 대비해 num는 9로
   1. 18~22번 줄 // 만약 d일 경우
   2. 정답에 가능한 숫자 경우의 수 곱함
   3. 수가 연속될 것에 대비해 num는 25로
   4. num는 10으로 초기화
4. 24번 줄 // 정답 출력

주의사항

1. 처음 ans를 0이 아닌 1로 둬서 경우의 수를 계속 곱해준다

https://www.acmicpc.net/problem/1725

https://www.acmicpc.net/problem/6549

1725: 2초 / 128MB

6549: 1초 / 256MB

문제 (6549)

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

• 가장 넓이가 큰 직사각형
• 1 ≤ n ≤ 100,000
• 0 ≤ h ≤ 1,000,000,000
• 직사각형의 너비는 1

풀이 (C++)

• cstdio
• vector
• stack

풀이 과정

1725와 6549는 출처가 완전히 같은 쌍둥이 문제

1725는 6549에서 반복문만 제거해주면 되므로 6549를 보자

높이 제한이 1000000000 (0이 9개)이고, N이 100000까지 가능하므로 높이를 기준으로 뭔가 하려는 순간 바로 시간 초과

고로 가로를 중심으로 보되 어떤 변화가 있는 부분( 높이의 대소관계가 변화는 지점 )을 중점적으로 본다

다음과 같은 입력이 있다고 가정하자

6 1 4 5 1 3 3

기본적으로 입력받은 순으로 스택에 넣는다

그 과정에서 일어날 수 있는 상황은 다음 두 가지밖에 없다

1. 넣으려는 수가 이전 수보다 크거나 같다 (빨간 화살표) => 스택에 push
2. 넣으려는 수가 이전 수보다 작다 (초록 화살표) => 스택에 있는 수들 중 넣으려는 수보다 큰 수들이 있는지 확인해준 후 push

특히 2번 경우를 잘 해결하는 것이 이 문제를 해결하는 것과 같다고 할 수 있다

이 상황이 언제 일어나는지 잘 기억해두자 ( 이하 '초록 화살표, 확인 상황'으로 통칭 )

확인하는 법

상황) 현재 i가 3이라서 i가 2일때 높이 (5)보다 높이 (1)이 작아서 확인하게 된 경우

스택에 들어있는 숫자들은 하늘색, 지금 기준이 되는 숫자는 초록색이라고 하자

1. i=2 일 때 만들 수 있는 최대 직사각형 = i=2일 때 높이 (5) x 너비 (3-1-1=1) = 5 (노란색)
2. i=1 일 때 만들 수 있는 최대 직사각형 = i=1일 때 높이 (4) x 너비 (3-1-0=2) = 8 (남색)
3. i=0 일 때 높이 = i=3일 때 높이이므로 확인 종료

이 과정에서 너비를 구하는 방법이 핵심이다

상황) 현재 i가 3이라서 i가 2일때 높이 (5)보다 높이 (1)이 작아서 확인하게 된 경우, 2는 이미 넓이 5로 확인 후 pop되었고, 다음 수인 1을 확인하려고 한다

1일 때 높이 4의 입장에서 보면 왼쪽에 0은 스택에 있고 오른쪽에 2는 스택에 없다

그리고 2는 현재 i인 3보다 작으므로, 높이 4보다 같거나 클 것임이 보장되어있다 ( 2의 높이가 만약 1의 높이보다 작았다면 이미 i = 2일 때 확인과정을 거쳐 스택에서 pop되었을 것이기 때문 )

따라서 높이는 4이고 너비는 좌우로 가능한 만큼 최대로 뻗어나갔을 때의 길이가 된다 (보라색선)

이때 가장 오른쪽은 현재 i 보다 1 작은 수일 것이고, 가장 왼쪽은 다음 stack에 맨 위에 있는 수+1일 것이다

$$ stack.top()+1 \leq x \leq i-1 $$

따라서 길이는 i-1-stack.top()

$$(i-1)-(s.top()+1)+1 = i-1-stack.top()$$

그런데 왼쪽에 더 이상 스택에 들어있는 수가 없을 수도 있다 이럴 경우에는 가장 왼쪽이 0이 되므로

$$ 0 \leq x \leq i-1 $$

따라서 길이는 i

1. 9, 12번 줄 // 0을 받기 전까지 무한 반복 구현
2. 14~16번 줄 // 수 입력받기
3. 18번 줄 // 정답 받아줄 변수 선언 ( 0으로 초기화, long long )
4. 19~28번 줄 // for문으로 가로를 기준으로 하나씩 확인
5. 20~26번 줄 // 이번 문제의 핵심! 
   1. 20번 줄 // while이 돌아가는 기준 잘 확인 ( 스택이 비어있지 않고 위의 "초록 화살표"일 경우 )
   2.  21~22번 줄 // 높이만 저장 후 스택에서 pop ( 이 시점부터 스택의 맨 위 stack.top()은 방금 뽑아낸 높이의 왼쪽에 있는 수 )
   3.  23~24번 줄 // 너비를 구해준다 ( 스택이 비었을 경우 i 아니면 i-1-stack.top() )
   4. 25번 줄 // 너비 * 높이로 넓이 구한 후 정답 변수 갱신 ( 이 때 형 변환 주의 !! )
6. 27번 줄 // 왼쪽에 있으면서 현재 높이보다 큰 경우를 모두 확인했으므로 push
7. 29~35번 줄 // 적절한 초록색 화살표를 만나지 못해 스택에 수가 남아있는 경우가 있다 이럴 경우에는 너비의 오른쪽 끝을 현재 i가 아닌 n으로 잡고 똑같은 while문을 돌려줌으로써 스택을 비워준다 ( 모든 경우의 수를 다 비교해본다 ) ( 제일 끝을 높이 -1의 임의의 초록색 화살표로 만들어 줬다고 생각하면 된다 )

주의사항

1. 넓이는 int범위를 넘을 수 있다
2. int와 int를 곱하면 long long이 되지 않는다. 곱하기 전에 형변환을 해 줘야 한다 ( 풀이에는 처음부터 높이를 long long으로 변환해둠으로써 처리 )
3. 정답 변수를 처음에 0으로 초기화해둬서 비교가 적절히 이루어지도록 한다
4. 1725에 제출할 때에는 반복문을 제거하자

https://www.acmicpc.net/problem/4948

2초 / 512MB

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

• N개의 물건 N(1 ≤ N ≤ 100)
• 무게 W W(1 ≤ W ≤ 100,000)
• 가치 V V(0 ≤ V ≤ 1,000)
• 최대 K무게 K(1 ≤ K ≤ 100,000)
• 배낭에 넣을 수 있는 물건들의 가치의 최댓값

풀이 (C++)

• iostream
• vector
• algorithm
• 동적 계획법

풀이 해설

동적 계획법으로 풀 수 있다

다음과 같이 구현할 수 있다 

예제 입력 1
4 7
6 13
4 8
3 6
5 12

3 7 
3 8 
1 5 
2 7

입력 받은 순서대로 살펴본다

1000000000(0이 9개)면 1초인데 대략 계산해보면

N*K = 10000000 (0 7개)이므로 충분히 2초 내에 작동함

1. 17~19번 줄 // 앞까지 도착한 숫자들은 전부 각 무게에서 여태껏 최대의 가치들이므로 이번 무게로 이행시켜준다 (빨간색 화살표)
2. 20번 줄 // 현재 물건의 무게가 최대 무게 이내일 경우 해당 무게의 칸에 이미 있는 값과 비교하여 큰 것을 넣어준다 (초록색 화살표)
3. 21~25번 줄 // 이전 숫자들을 보면서 이번 무게와 합쳤을 때 최대 무게를 넘지 않는 경우에는 해당하는 무게의 칸에 이미 있는 값과 비교하여 큰 것을 넣어준다 (파란색 화살표)
4. 28~30번 줄 // 맨 마지막 물건을 한번 돌면서 정답을 찾아낸다

주의사항

1. 저장하려는 위치에 이미 수가 있을 수도 있으니 꼭 비교해서 더 큰 수만 저장하도록 해야 한다
2. dp는 0으로 초기화 해준다 (풀이 해설 2번에서 비교할 때 없는 경우를 0으로 비교해야 하므로)
3. dp[i-1]과 같은 경우 segmentation fault (dp[-1] 참조) 발생할 수도 있으니 꼭 맨 앞 배열 한 칸은 비워둔다
4. dp 배열이 커서 segmentation fault가 날 수도 있다 -> 전역 범위로 (main 밖) 빼준다 // BOJ에서는 통과했다