백준에서 똑같은 문제 7570_줄세우기는 실패했다.. 이유는 무엇일까?
이 문제는 정말 어떻게 푸는지를 몰라서 헤맸고, 결국 인터넷을 통해 풀이법을 공유 받았는데도 이해가 안 가는 문제다.
학생들의 번호를 인덱스로 가지는 배열을 가지고 동적계획법을 활용한 문제인 것은 같으나
그 로직에 대해서 100% 이해가 가지 않는다.
우선, 문제의 핵심은
줄을 세울 때 맨 뒤로 보내거나, 맨 앞으로 보내는 개수의 최소 값을 구하라는 것인데
가장 긴 증가하는 학생들의 수열을 구한 후에 전체 학생 수에서 빼주면 그 것이 최소로 학생들을 맨 뒤로 보내거나,
맨 앞으로 보내게 되는 것이었다.
대충 이해는 가겠으나, 이 것을 코드를 옮기는데 잘 되지 않아,,,(예제 테스트케이스는 맞았으나 그 다음부터 잘 안되어서
다른 코드를 참고 했는데, 보고도 잉?)
나와는 다르게 입력 받은 번호를 인덱스로 활용해서 동적으로 학생들의 증가하는 수열을 구하는 방법이었다.
예제의 테스트케이스를 이용해 설명하자면
5
5 2 4 1 3
1) 입력 5가 들어왔을 때
dy[5] = dy[5 - 1] + 1 // 4번째 학생까지 연속되는 수열 개수 + 1
dy[2] = dy[2 - 1] + 1 // 1번째 학생까지 연속되는 수열 개수 + 1
dy[4] = dy[4 - 1] + 1 // 3번째 학생까지 연속되는 수열 개수 + 1
dy[1] = dy[1 - 1] + 1 // 0번째학생까지(0번째학생은 없다) 연속되는 수열 개수 + 1 => 1
..
입력되는 순서 대로 값이 들어갈 것이므로 완전 머리를 잘 쓰신 분이 짜신 코드 같다.
