처음에는 무슨 그래프로 완전 탐색하는 건가 생각했다... 그러다가 문제 분류를 봤는데 dp라고 되어있어서... 아 난 정말 너무 부족하다...휴 여튼 dp로 접근하려고 생각해보니 작년 2학기 알고리즘 시간에 비슷한 dp문제를 푼적이 있다는 게 기억이 났다.
그래서 어떻게 풀어야할지 감은 왔는데... 문제는 입력 값인 삼각형 형태의 숫자들을 어떻게 담을 것이며 dp로 풀기위해 삼각형을 트리라고 보면 child가 parent가 누구인지를 알아야 하는데... 이걸 배열에 담으면.. 어떻게 index를 구분하지..부터... 그냥 복잡해졌다...
어떻게 풀어야할지는 알고 있는데.. 저것을 어떻게 받을지 어떤 자료형을 쓸지... 어떻게 표현할지 전혀 감이 안왔다...
아 정말 난 실력이 너무 부족하고 너무 못하는데... 말로만 그러고 실제로는 자만심에 빠져있다. 너무 오만하다... 그러다보니 여유부리고.. 벌써 4월 20일... 휴...
자신이 나약한지 알아야 강해질 수 있다는데 난 내가 나약하다고 입으로만 말하지 실제로는 잘한다고 생각하고 절실히 느끼지는 못하고 있다...
열심히 하자...
여튼 그래서 구글링을 해서 다른 사람의 코드를 참조했다.
그래서 2차원 배열에 넣고 쉽게 풀었다.
그리고 맞은 사람 목록에서 다른 사람의 코드를 봤는데.. 그냥 일차원 배열로도 풀 수 있었다... 그리고 나는 맨 끝에 있는 숫자의 경우 자신의 parent를 찾을 때 parent가 하나 밖에 없으므로 조건을 걸어줬는데, 그럴 필요가 없었다. 어차피 index를 1부터 시작하면 0부분은 비어있고, 끝 부분+1부분도 비어있다.. 아마 0으로 초기화 되있을 것이다. 0으로 초기화 하면된다. 이게 최대값을 구하는 것이므로 0으로 초기화 해놓으면 다른 조건 필요없이 parent를 2개로 생각하고 그 중 최대값을 얻으면 된다...
최소값을 구하는 거라면 엄청 큰 수로 초기화 해놓든가 하면 될 것이고...
열심히 하자.
강해질 수 있는 방법은... 자기 자신이 얼마나 나약한지 아는 것이다. (드래곤사쿠라)
댓글 없음:
댓글 쓰기