5월 10일 백준

* 코드는 맨 아래에 있습니다

참교육의 연속...

# 백준 1005번: ACM Craft

위상 정렬이라고 나오는데 단순 재귀로도 풀린다. 사실 둘이 근본적인 차이가 없긴 하다.

# 백준 1006번: 습격자 초라기 (실패)

초심자의 덫이라고 불린다는 습격자 초라기에 결국 나도 초심자임을 증명해버렸다.

오늘 주구장창 7시간 정도 계속 한 것 같은데 결국 못 풀었다.

접근법은 다음과 같았다.

인접 노드 중 합이 W보다 작은 애들을 이으면 그래프가 나오는데,

그 그래프에서 노드 두 쌍씩 짝지을 수 있는 최대 경우를 구하면 될 것 같았다.

여기까지는 맞다. 그런데 어떻게 구해야 하나..

노드가 제일 적게 연결되어 있는 노드부터 차례로 제거해나가는 알고리즘이면 될 줄 알았는데, 반례가 계속 나왔다.

아래가 가장 대표적인 반례..

무당벌레 같다... ㅠㅠㅠ

DP문제라는 것은 알고 있었는데 어떻게 접근할지 감도 안오고, 내 방식대로 푸려고 했지만 결국 결과가 좋지는 못했다. 아쉽다. 내일 마저 도전할 것이다.

쉬운 문제를 푸는게 더 도움이 되었을까.. 시간을 너무 많이 써버렸다.

모르는 것이 너무 많은 것 같다. 내일은 더 열심히 공부해야겠다.

코드 공유는 안하려 했는데 그냥 볼 사람 보세요. ^~^ 뭐 대단한거라고..

코드 깔끔하게 짜는 건 포기. 모로 가든 푸는 데 의미를 두는거로. 불필요한 부분이 들어가있을수도 있습니다.

코드는 테스트케이스 비교용으로만, 혹은 자신이 놓친 부분 찾는 것 정도로만 사용하길 바랍니다. 기왕이면 보지 마시고 자신의 힘으로 푸시길 바래요. 생각하는 과정이 없으면 인생에 일절 도움이 안됩니다. 특히 랭작용으로는 사용하지 말아주세요

1005.cpp