ownvoy   1년 전

일단 재귀로 풀었습니다.  

A타워랑 B타워가 있을 때 Input 받은 거를 A타원 기준으로 오름차순으로 정리해줬습니다. 

ex)

1 8                        1 8
3 9                        2 2
2 2                        3 9
4 1                        4 1 
6 4                        6 4
10 10                      7 6
9 7                        9 7  
7 6                        10 10

그 후 [1,8]부터 시작해서 자신과 꼬인 것이 있으면 둘은 공존할 수 없으니, 새로운 A,B 타워에 보내줬습니다.(예를 들어 2,2)

이런 식으로 반복문을 돌린 후, 그리고 기존의 A,B의 선의 개수를 전역변수 result(리스트)에 넣었습니다.

이 과정을 반복합니다. 

(새로운 A,B에도 꼬인 선이 있을 수 있으니, 또 새로운 A,B 타워를 만들어 그 곳에 하나를 보내줬습니다.

다 보낸 후 기존 타워의 선의 개수를 리스트에 넣어주고요.)

이런 식으로 result 값을 추가하면서 더 이상 꼬인 것이 없을 때, max(result)를 return 해줌으로써, 공존할 수 있는 최대의 선 개수를 return 했습니다.

추가로 새로운 타워에 꼬인 선을 넘기는 과정 중에 안 꼬인 선을 넘기는 과정이 없었습니다.

(원래부터 안 꼬인 선은 기존의 타워에도, 새로운 타워에도 존재할 수 있습니다.)

최대한 많은 수의 선을 살려야 함으로 안 꼬인 선도 같이 넘겨주는 과정을 추가해줬습니다. 

댓글을 작성하려면 로그인해야 합니다.