Red Salmon

출처 : https://www.acmicpc.net/problem/2294

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/2294.cpp

동전문제...

대놓고 나  DP입니다. 하는 문제이다. 정말 자주나오는 패턴이며 DP의 기본이라 할 수 있다. 

이 기본틀을 가지고 이렇게 저렇게 참 많이 바꿔서 문제가 나온다. 결국 다 비슷한 문제이며, 키워드만 정확히 이해하면 쉽다.

푼지는 꾀 되었으나 복습차 풀어봤다.

결국은 그거다. 동전 하나를 놓고 그 동전으로 만들수있는 경우의 수를 다 만든다. 그 다음에는 다음 동전으로 똑같은 경우를 체크하면서 쭈욱 확인한다. 핵심은 바로 이문장인데

	for (int i = 0; i < n; i++)
		for (int j = coin[i]; j <= k; j++)
			cnt[j] = min(cnt[j], cnt[j - coin[i]] + 1);

이 문장을 살펴보면 cnt[j] 값을 계속 갱신하는데 j는 그냥 값 그 자체이며 cnt[j-con[i]] 는 3원을 구하려면 10원에서 7원을 빼면 된다. 뭐이런거랑 똑같은거다. 그런식으로 갱신을 해나간다. 물론 뒤에 +1을 하는건 현재 자기 자신을 추가하려는 것이기 때문이다.

알아두면 참 편리한 기본이다. 

출처 : https://www.acmicpc.net/problem/2513

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/2513.cpp

쉽게 생각하고 접근했다가 조금 해맸다.

나는 학교를 기준으로하여 왼쪽 파트와 오른쪽 파트를 나누었다. 

중요한 부분은 다채웠을때와 다 채우지않았을때를 정확히 구분하고 버스가 학교를 갔다가 다시 돌아올때 어느 지점으로 컴백하는지가 중요했다. 잘 생각해보면 햇갈리지 않을 것이다.

그러나 딴짓하면서 하다가 많이 놓친문제이다. 문제는 집중해서 풀어야겠다.

출처 : https://www.acmicpc.net/problem/1268

정답 : https://github.com/stemp12/acmicpc.net/blob/master/2016.02/1268.cpp

대충 보면 복잡해 보인다. 하지만 인풋에 초점을 두자. 학년은 5개 뿐이다. 학생수는 최대 1000명이다. n^2이면 1000000이고 여기에 5를 곱하니 5백만이 된다. 이정도면 무난하게 전부 조사를 해보면 될거 같다.

또한 간단히 체크하기 위해서 1000명이라고 했으니 1000 x 1000배열도 사용 가능하다는것을 알았다.

그럼 그래프처럼 학생들끼리의 표를 만들어 한명이 몇명까지 컨텍이 되는지 체크한다. 그리고 출력하면 된다.

어려워 보일수도 있으나 인풋만 집중하면 된다.

출처 : https://www.acmicpc.net/problem/2526

정답 : https://github.com/stemp12/acmicpc.net/blob/master/2016.02/2526.cpp

예전에 풀었던 문제이다. 근데 재채첨으로 오답이나와서 다시풀어줬다.

결국 키워드는 p로 나눠주는데 이게 97이므로 어떤 수가 나와도 결국 97아래의 숫자끼리 중복이 일어난다는 말이다. 그리고 그 중 하나의 숫자라도 있으면 다시 반복이 된다는것이 키워드다.

그 처리만 해주면 되는 매우 쉬운 문제이다.