지하철에서 찌글찌글하게 해보다가 일단 정렬을 해보자는 식으로 나가보았습니다.
얼추 되겠다 싶었는데, 아래의 과정 5에 해당하는 부분을 생각해내기가 좀 힘들었습니다.
<과정>
1. 각각 입력된 종이의 가로 세로 길이 중 작은 값을 앞에 놓고, 큰 값을 뒤에 놓는다.
2. 1에서 얻어진 결과 중 앞의 값을 기준으로 모든 종이를 오름차순 정렬한다.
3. 2에서 얻어진 결과를 기준으로 현재의 종이와 앞의 종이를 비교하여, 앞의 종이를 현재의 종이에 올려놓을 수 있는 크기인지 판단한다. (판단 기준은 1에서 얻어진 큰 값)
4. 앞의 종이를 현재의 종이 위에 올려놓을 수 있다면 카운트를 증가시킨다.
5. 4의 경우에, '앞의 종이에 올려놓을 수 있는 종이의 장수'가 '현재 종이에 올려놓을 수 있는 종이의 장수' 보다 작으면 카운트를 증가시키지 않는다.
(' 현재의 종이'의 '앞의 종이'가 '현재의 종이'위에 올려놓을 수 있다고 하더라도, '앞의 종이'에 올려놓을 수 있는 종이가 '현재의 종이'위에 올려놓을 수 있는 종이보다 작다고 하면, '앞의 종이'를 ‘현재의 종이’에 올려놓는 것은 최고로 많이 쌓을 수 있는 종이의 기준에 미달하게 된다.)
6. 이렇게 구해진 각각의 종이에 올려놓을 수 있는 종이의 장수 중 가장 큰 값을 출력한다.
1. 각각 입력된 종이의 가로 세로 길이 중 작은 값을 앞에 놓고, 큰 값을 뒤에 놓는다.
2. 1에서 얻어진 결과 중 앞의 값을 기준으로 모든 종이를 오름차순 정렬한다.
3. 2에서 얻어진 결과를 기준으로 현재의 종이와 앞의 종이를 비교하여, 앞의 종이를 현재의 종이에 올려놓을 수 있는 크기인지 판단한다. (판단 기준은 1에서 얻어진 큰 값)
4. 앞의 종이를 현재의 종이 위에 올려놓을 수 있다면 카운트를 증가시킨다.
5. 4의 경우에, '앞의 종이에 올려놓을 수 있는 종이의 장수'가 '현재 종이에 올려놓을 수 있는 종이의 장수' 보다 작으면 카운트를 증가시키지 않는다.
(' 현재의 종이'의 '앞의 종이'가 '현재의 종이'위에 올려놓을 수 있다고 하더라도, '앞의 종이'에 올려놓을 수 있는 종이가 '현재의 종이'위에 올려놓을 수 있는 종이보다 작다고 하면, '앞의 종이'를 ‘현재의 종이’에 올려놓는 것은 최고로 많이 쌓을 수 있는 종이의 기준에 미달하게 된다.)
6. 이렇게 구해진 각각의 종이에 올려놓을 수 있는 종이의 장수 중 가장 큰 값을 출력한다.
글로 설명하려니 뭔가가 좀 이상합니다.
깔끔하게 계산 과정을 표로 정리해보았습니다.
표로 보시는게 이해가 빠를겁니다.
좌우당간 보고서도 간단하게 쓰고 끝내렵니다.
다음에는 또 어떤 어려운 문제가 나올지 벌써 부터 걱정이네요.
김철호PAPER.zip수정사항
중간쯤에 보면 if(array[i][0]<array[j][0]) 이 부분이 있는데
if(array[i][0]<array[j][0] || (array[i][0]==array[j][0] && array[i][1]<array[j][1]))
위의 것으로 바꿔줘야 합니다.
TAG 알고리즘
댓글을 달아 주세요
헐, 이런 것들 어떻게 푸시는지 정말로 궁금합니다 ㅠㅠ
알고리즘 초초짜를 위해 추천해 주실 책 있으신지요? ㅋ
교수님께서 이건 아무것도 모르는 상태에서 알고리즘 이용없이 그냥 해보는게 좋다고 하셨습니다.
참고로, 이건 2학년 2학기 과목이고요.
저는 지금 3학년 2학기... -_- 알고리즘은 개뿔도 모르고요.
답이 나와서 그런지 이건 꽤나 아주 쉬운 문제더라고요.;;