백준/애드혹,구성적 (5) 썸네일형 리스트형 [ICPC] 백준 14961 - Untangling Chain https://www.acmicpc.net/problem/14961 관찰 같은 방향으로 가는 경우가 없다. 무조건 회전한다. 어쩌면 이를 이용해서 무언가 할 수 있을지도 않을까? 예제 tc 2번을 그려보자. 이처럼 겹치는 부분이 한 번 발생한다. 이를 해결하려면 어떻게 해야 할까? 가장 명확한 방법은 위에서 2만큼 이동하는 부분을 4로 조정하면 된다. 이를 유심히 보자. 밑으로 내려가기 전엔 왼쪽 방향으로 이동을 했었다. 밑으로 내려갈 때 교차가 일어나지 않으려면 왼쪽으로 이동할 때 충분히 이동해야 한다. 얼마만큼? 방문했었던 좌표 중에 가장 작은 x 좌표보다 1 이상 더 이동해야 한다. 이를 일반화 해보자. 이번에 아래 방향으로 이동을 한 상태라면 다음 이동은 왼쪽 또는 오른쪽으로 할 수밖에 없다. 그.. 백준 12095 - 가장 오래 걸리는 스도쿠 https://www.acmicpc.net/problem/12095 스도쿠는 백트래킹으로 풀기 힘들다는 사실을 배우는 문제이다. 스도쿠를 결정적으로 빨리 푸려면 크누스 X 알고리즘을 사용해야 한다. 밑의 스택 오버플로우 링크에서 백트래킹에 의한 스도쿠 풀이가 느린 경우를 제시하니 살펴보면 좋을 것이다. https://stackoverflow.com/questions/24682039/whats-the-worst-case-valid-sudoku-puzzle-for-simple-backtracking-brute-force-al What's the worst-case valid sudoku puzzle for simple backtracking brute force algorithm? The "simple/na.. 백준 13269 - 쌓기나무 https://www.acmicpc.net/problem/13269 힌트 더보기 만드는 게 우선이다. 일단 주어진 조건에서 가장 적절한 배치를 만들어라. 해설 더보기 위에서 본 view(이하 top_view), 앞으로 본 view(이하 front_view)와 옆에서 본 view(이하 side_view)가 주어질 때 가능한 상태인지 확인하고 실례를 출력하는 문제이다. 일단 top_view를 입력 받는다. 다음으로 front_view와 side_view를 받으면서 top_view[i][j]의 상태와 front_view[j], side_view[i]의 상태가 모순인지 확인한다. side_view는 왼쪽에서 본 순서로 주어진다는 것을 유의한다. 예를 들어서 설명하면 top_view[i][j]가 0인데 front.. 백준 13019 - A를 B로 https://www.acmicpc.net/problem/13019 풀이 일단 서로 가지고 있는 문자가 다르면 문제에 제시된 연산으로 같게 만드는 것이 불가능하므로 -1을 출력한다. 위 조건을 통과하면 답의 초기값을 0으로 설정하고 B의 맨 뒤와 A의 맨 뒤에 포인터(index)를 둬서 서로 비교한다. 둘이 같지 않으면 A의 마지막을 맨 앞으로 보내야 하는 것은 자명하므로 앞으로 보냈다 치고 답을 1 증가시킨다. 두 포인터가 같다면 B의 포인터는 더 볼 의미가 없으므로 B의 포인터에 1을 뺀다. A는 뭐가 되었든 1을 빼면서 모든 문자를 순회한다. 이렇게 A를 순회하면서 증가시킨 값들이 최종 답이다. 뭐? 도대체 무슨 소리를 하고 있는 건지 이해하지 못할 수 있다. 예제 케이스 1번을 보자. 위 방법대로.. 백준 2873 - 롤러코스터 https://www.acmicpc.net/problem/2873 분석 문제를 잘 이해하면 가능한 한 지날 수 있는 모든 칸을 지나야 하는 문제임을 알 수 있다. 이 문제의 격자를 체스판으로 생각한다. 시작하는 지점을 흰 칸이라고 가정하자. 그러면 각 이동마다 흰 칸 -> 검은 칸 -> 흰 칸 ->... 이 반복되고 이동을 시작하는 시점에는 지금까지 흰 칸을 지나간 횟수 = 1, 지금까지 검은 칸을 지나간 횟수 = 0 상태가 된다. 이를 이해하면 흰 칸을 지나기 위해선 지금까지 흰 칸을 지나간 횟수 = 지금까지 검은 칸을 지나간 횟수를 만족해야 하고 검은 칸을 지나기 위해선 지금까지 흰 칸을 지나간 횟수 + 1 = 검은 칸을 지나간 횟수를 만족해야 함을 알 수 있다. 이를 토대로 문제를 해결하기 위해 두.. 이전 1 다음
