memo 배열 선언은 유연하게 && 추가연습이 필요하다 BOJ1949 우수 마을 – DP 시

 https://www.acmicpc.net p roblem1949~1949번 제출을 맞은 사람 쇼트 코딩, 수영장 작성 등의 요청 재채점 수정 채점 현황 강의 우수 마을의 시간 제한 메모리 제한 제출 정답 정답의 비율 2초 128MB182577945349.186%문제 N개의 마을에서은 나라가 있다. 편의상 마을에는 1에서 N까지 번호가 붙어 있다고 한다. 이 나라는 트리 구조로 되어 있다 즉, 마을과 마을 사이를 직접 묶는 N-1개의 길이 있으며, 각각의 길은 방향성이 없고 A 번 마을에서 B 번 마을에 갈 수 있다면, B 번 마을에서 A 번 마을에 가라. 또 모..www.acmicpc.net의 초반은 무조건 우수한 마을과 열등한 마을은 인접하고는 안 된다고 생각하고”흑 적 트리?”라고 생각했다.나중에 검색하면 모든 트리는 이분 그래프에서 인접한다없이 두 가지 색으로 바를 수 있다는 거였다.

어쨌든 우수촌끼리만 인접해야 하고 다만 열등촌은 적어도 한 우수촌과 인접해야 한다는 문제다.다시 말해 우수촌은 인접해선 안 되고 열등촌은 3칸 이상 연속해서도 안 된다.DP 문제를 푼 사람이라면 뭐가 보일지도 몰라.

https://blog.naver.com/webserver3315 처음에는 어떻게 해야할지 몰랐고, 특히 3단 연속 올라가는 것이 불가능조건을 어떻게 BFS로 실현해야할지 몰랐고…blog.naver.comhttps://blog.naver.com/webserver3315/221695420153https://blog.naver.com/webserver3315도 4개월전에 풀었던 문제다.그때도 세 칸씩 묶어서 이… blog.naver.com 호옹이?

계단을 오르는 문제와 비슷하다. 그뿐 아니라 연산량 또한 DP를 적용하지 않으면 아마 풀기 어렵게 만들어져 있을 것이다. 우선 노드수는 1의 4승, 즉 1만개다.

예전에 계단 오르는 문제를 풀 때 비슷한 유형이었던 게 생각났다.

1차원인 계단의 가중치 값을 “서브트리”의 가중치로서 생각하면 역시 1차원이다.

하지만 이렇게까지 떠올린 것은 좋았지만 이번에는 그 경험이 독이 됐다.예전에 우리가 계단을 올라가는 문제를 풀 때,

해당 계단을 밟았을 때의 최대치, 해당 계단을 밟지 않았을 때의 최대치

이렇게 2원화하고 memo 배열을 유지하려고 풀다가 피땀이 나 정신을 차려보니 밟았을 때의 최대치만 손에 넣으면 되었다는 생각이 들었다.따라서 해당문제 또한 memo 배열을 2원화하는 것은 함정의 지름길이라고 생각하여 memo 배열을 “해당 노드를 색칠했을 때 해당 노드의 서브트리로부터 얻을 수 있는 최대우수인구수”로 정의하여 1원화하여 풀기로 하였다.

자신만만한 나의 점화식은(※참고로, 자노드는 여기에서는 반드시 레벨 1만 낮은 노드를 의미한다. 즉 손노드는 자노드가 아니다!”

memo[x]의 정의: 노드x를 우수 마을에 픽한다고 가정했을 경우 최대 인구수

답방법: 1. 해당 노드를 색칠하지 않으면 안 되기 때문에 일단 자노드의 인구수는 체에 걸러야 한다. 절대로 더할 수 없기 때문에. (우수마을 인접 금지) 2. 그러면 孫노드값이 승계되거나 증손노드값이 승계되거나 둘 중 하나다.3. 각 손노드의 서브트리에 대해서 4.max(해당 손노드에 각인된 memo값, 해당 손노드의 자노드의 memo값의 합) 5.를 모든 손노드에 대해서 실시하고, 더해, 6.픽 한다고 했으므로, 마지막에 본인인구를 더한다.7. 최종적으로 1번 노드를 루트 노드라고 했을 때, 8. max(1번 노드에 각인된 memo값, 1번 노드의 모든 자식에 각인된 memo값의 합)가 답이다.그 결과 https:/github.com/webserver3315/Desktop_PS_BOJ/blob/master/PS_BOJ 데스크톱_백준공부용. Contribute to webserver 3315Desktop_PS_BOJ development by creating an account on GitHub.github.com 테스트 케이스 및 자체 제작 테스트 케이스까지 모두 합쳤으나 대항해서 꼬였다.왜 틀렸는지 감이 오기도 하고 안 올 것 같기도 한데(특정 손자 노드의 좌자는 고르고 우자는 빼는 선지가 최적이라면 그게 예외일 수도 있겠다는 생각을 잠깐 해봤다.)

시험 케이스 제작이 힘든 해당 문제의 특성상 1시간 동안 뚫려 있었는데 답이 없는 것은 답이 없다고 판단해 다른 블로그를 참조하다 기습을 당했다.

DP는 밟았을 때 및 밟지 않았을 때의 각각의 memo[ ]변수로, 별도 유지하는 것이 오히려 시원하고 효과적일 때가 있다는 것을 처음으로 깨달았다.전에 화상을 입은 적이 있어서 절대 그런 일은 없을 거라고 생각했는데 착각이었어.상황을 보면서 해야 한다. 유연함이 매우 중요한데 그러지 못했기 때문에 이렇게 생각하면 참으로 쉬운 문제에 이상하게 접근하고 만 것이다.

간단하고 확실하게 해야만, 특히 알고리즘의 문제일 경우 요격할 여지가 적어 깔끔하다는 것이 중요하다.어쨌든 이 블로그를 참조한 결과 suuntree.tistory.com:/www.acmicpc.net/problem1949번: 우수마을의 1행에 정수 N이 부여된다. (1≤N≤10,000) 2행에는 마을 주민수를 나타내는 N개의 자연수가 괄호를 넣어 부여된다. 1번가에서 N..suuntree.tistory.com 공부하는 곳이 꽤 있네.일단 이게 될 줄은 처음 알았어.지금까지는 밖에 안된다고 생각했는데.물론 10000*2로 선언하는게 20000보다 메모리적으로 좋지 않지만(‘문자가 쓸데없이 자꾸 들어가버려서’ 편한건 전자고, 전자의 경우 memset에서 for문 10000번 돌릴 필요도 없이 원큐가 되는게 신기했고,

또, 로 1 차원 변수를 true에 접근할 수 있는 것도 처음으로 알았다.형 변환 오류 나는 줄 알았는데 char 그냥 넘어가 주는 거야.

아무튼 https://github.com/webserver3315/Desktop_PS_BOJ/blob/master/PS_BOJ 데스크톱_백준공부용 Contribute to webserver 3315Desktop_PS_BOJ development by creating an account on GitHub.github.com의 구현을 도용하여 과감히 ret 변수만을 두고, 위의 허브 코드에 있던 ans 값을 날리면 오히려 훨씬 낫다.DP 따로 연습해놔야 돼.특히 탑 다운