Red Salmon

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

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

얼핏보면 굉장히 어려운 문제 같다. 하지만 잘 보면 어렵지 않다.

dp인듯하지만 아주 기초적인 부분만 물어보고있다.

문제의 요점은 큰녀석이 가장 밑에 깔리고 점점 더 작은 녀석이 위로 올라가는데, 여기서 포인트는 겹점을 허용하고 있다는 말이다. 

먼저 전체 인풋을 정렬을 시킨 후에 현재 사각형이 얼마나 위에 올라오는지 차곡차곡 저장시킨다. 그리고 모든 사각형에 대해서 계속 최대값을 갱신하는 식으로 하면 가장 큰 값을 저장시킬수있다. 

그리고 마지막에 자기 자신을 올려주는 식으로 진행하면 된다.

그렇게 어렵지 않은 문제이다. 왜냐면 이건 초등부 문제이기 때문이다.

출처 : 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/11441

정답 : https://github.com/stemp12/acmicpc.net/blob/master/2016.01/11441.cpp

이 문제의 풀이는 이미 내가 과거에 풀어본 배열내 구간 계산이므로 세그먼트 트리를 적용시키면 된다. 설마 이 문제를 읽고 구간 a부터 b까지의 합을 계속 더하고 더하고 하는 사람은 없을것이다. 무조건 TL이 나올것이다.

세그먼트 트리도 정답이지만 이 문제는 조금 더 생각하면 다른 해법도 있다.

어차피 구간내의 합이기 때문에 0부터 계속 더해나가는 것이다. 즉

a[0]=a[0]

a[1]=a[1]+a[0]

a[2]=a[2]+[1]

a[3]=a[3]+a[2]

이렇게 하면 구간 0부터 n까지의 합이 계속 저장이 된다. 그리고 입력으로 구간이 입력이 되면 그 구간을 빼주면 된다.

즉 a~b구간의 합은 0~b구간의 합에서 0~a구간의 합을 뺀다면 a~b구간의 합이 되는것이다. 이렇게 푸는것도 간단히 푸는 방법이다.

그러나 나는 세그먼트트리 연습겸 저렇게 풀어봤다.

이런 문제가 참 괜찮은 문제라고 생각한다.