Red Salmon

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

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

이문제와 거의 같다.

그래서 다시 bool변수로 바로바로 체크하게 하였고 결과적으로 정답을 맞았다. 그런데 bool함수를 더 두어 가로세로부분도 포문없이 검색하게하였다면 속도가 더빨라졌을거라고 생각한다.

굉장히 귀찮고 손이 많이 가는 문제였다. 하지만 기초적이고 생각할게 있는 괜찮은 문제라고 생각한다. 

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

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

과거에 풀었으나, 재채점으로 오답이 나와서 다시 풀었다.

알고리즘은 참 쉽다. 마이너스도 있고 플러스도 있는데 연속된 구간이 가장 큰 값을 찾는것이다.

방법은 0부터 차례대로 더해가면서 MAX를 계속 갱신하고, 값이 감소하면 카운팅을 다시 처음부터 하는 것이다.

이런식으로 전개를 하다보면 결국 MAX가 담기게 된다.

문제는 전부 마이너스로만 이루어질때인데 아마 이부분때문에 오답이 나온거 같다.

-1 -2 -3이 인풋이라면 최대값은 -1이 되는것이다.

다행히 틀린점을 빨리 찾은 문제였다.

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

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

정말 생각을 많이 했던 문제이다. 우선 N이 1000자리라고 한다. 엄청나게 큰수이므로 문자열로 받아야 한다.

그런데 이건 이진수다. 뭔가 규칙이 반드시 있다는 말이다.

17N은 16N+N이다. 그리고 16N은 이진수로 뒤에 0000붙인것과 같다. 즉 인풋으로 들어오는 값에 0000을 붙이고 원래의 인풋을 더해주면 끝이난다.

계산이 매우 간단해지며 이진수 덧셈만 구하면 끝나는 문제이다. 

방법만 생각하면 금방 풀 수 있는 문제이다.

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

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

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

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

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

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

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

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