2565번 전깃줄(DP) -☆

#문제링크 : https://www.acmicpc.net/problem/2565

<전략>

1. LIS(가장 긴 증가하는 부분수열)의 응용문제다. 

2. 1번 전봇대의 전깃줄 위치번호를 인덱스라 생각하고, 해당 위치번호와 연결되어있는 2번 전봇대의 위치번호를 그 인덱스의 값이라 생각해보면, 인덱스가 증가할때, 값도 증가하는 수열중, 즉, 가장 긴 증가하는 부분수열을 찾아낸후, 전체 전깃줄 갯수에서 빼주면, 제거해야할 전깃줄의 최소 갯수를 구할 수 있다.

※주의사항

1. 처음에 d배열(메모이제이션)을 0~100까지 초기화하고 a배열(문제에서 주어진 전깃줄)을 0~500까지 초기화했는데, 이런 사소한 부분에서 실수하지 않도록 하자.

2. 전깃줄의 갯수(n)까지만 반복해서 메모하는 것이 아니라, 주어진 전깃줄 번호중 가장 큰 번호까지 조사해봐야 한다. 문제를 자세히 보면 전깃줄 갯수와 상관없이 위치번호가 부여된 것을 볼 수 있다. (연결되지 않은 위치도 있다.)

3. cin>>j>>a[j];와 같은 코드는 입력 인식이 안된다. j까지는 들어가지만, j값이 완전히 인식되지 않았기에, 코드 한줄을 추가해서, 즉, cin>>j; cin>>a[j]; 와 같이 세미콜론으로 구분 짓고 입력받도록 하자.

Code