언제쯔음

보호되어 있는 글입니다.

https://www.acmicpc.net/problem/1967문제의 초점을 트리보다는 직관적인 부분을 고려해서 문제를 설명해보려고 한다.증명보다는 이미 알고 있는 지식, 직관으로부터 문제를 해결해보자.문제에서는 정점끼리의 가장 긴 길이를 물어보고 있다.위 그림에서 가장 긴 선은 무엇인가? A와 C를 잇는 선이다.왜? AC 선분이 제일 길까? 그냥 제일 길어서다.긴 선분보다 정점의 관점에서 다시 바라보자.가장 멀리 있는 정점 2개를 고르면 가장 긴 길이를 갖는 선분을 가지게 된다.그렇다면 가장 멀리있는 정점 2개를 어떻게 고를까?A에서 C가 가장 멀다.B에서 C가 가장 멀다. D에서 C가 가장 멀다. C에서 D가 가장 멀다.가장 먼 정점은 어느 정점을 골라도 2개로 좁혀진다.이에 대한 설명을 귀류법으로..

https://www.acmicpc.net/problem/1043지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일..

https://www.acmicpc.net/problem/17070문제를 읽다보면 입력 값에 N(3 ≤ N ≤ 16)란 정보를 알 수 있다. 해당 정보에 따라 무언가 백트래킹으로 해결이 가능함을 엿볼 수 있다.그도 그럴게 파이프는 계속 오른쪽으로 옮겨지니, 경우의수가 적지 않을까 싶은 생각도 있었다.다만 이전과 다르게 해당 문제는 파이프가 2개의 칸을 차지 하고 있는 이미지로 인해 어떻게 백트래킹을 구현할 수 있을지 고민이 된다.=> 2개의 좌표로 인해 백트래킹이 어렵다면, 일단 하나의 좌표로 백트래킹을 구현할 수 없는지 고민해보았다.결국 다음 좌표를 결정하는 것은 오른쪽, 아래 등 이동한 좌표의 지점이다. 그렇기 때문에 해당 좌표만 가지고 백트래킹을 구현해보면 간단하게 해결 가능하다.그리고 백트래킹을 ..

https://www.acmicpc.net/problem/15686생각의 흐름1.최대 M개를 고르라는 말의 의미는 무엇이지?=> 최대 M개를 안 고르는 경우도 있나?2. 치킨집을 제거한다고 하는 경우, 다른 치킨집의 거리에 영향이 가는가?=> 좌표로 계산하기 때문에 영향이 없음.=> 1번은 모르겠으나, 2번의 특성을 본다면, 모든 경우의 수를 탐색해서 계산하면 그만이겠다는 생각이 들었다.=> 조금 느릴 것 같은데, 빠르게 하는 방법은 없을까? => 그리디?근데 N이 50이라 워낙 수가 작아서 총 칸이 250이고, 집은 커봐야 2N이라 100 밖에 안 된다는 생각에 모든 경우의 수를 구하려고 했다.=> 마음에 걸리는 요소는 1번, M개 이건 뭐지?조합.. 😑 👍조합을 구현하고, 계산의 요소를 추가한 문..