백준/애드혹,구성적 (7) 썸네일형 리스트형 백준 1069 - 집으로 https://www.acmicpc.net/problem/1069힌트더보기제목 그대로 집으로 가는 방법은 몇 개가 있을까? 넓은 관점으로 생각해본다.풀이더보기다음 그림을 보면 이 문제에 대한 핵심을 쉽게 이해할 수 있다. 위 그림을 보면 알 수 있듯이, 목표를 향해 일직선으로 가는 것보다 점프를 2번 해서 가는 방법이 더 빠른 경우가 존재할 수 있다. 우리는 이 사실을 반영하여 목표로 향하는 최소 시간을 구하기 위해 다음 두 방법을 섞었을 경우를 계산할 것이다. 1. 목적지까지 일직선으로 걷기 또는 점프하는 시간2. 목적지에 도착하기 위해 두 번 점프하는 시간 일단 초기해를 피타고라스의 정리로 계산한 두 지점 간의 일직선 거리 $(dx^{2} + dy^{2})^{\frac{1}{2}}$로 설정한다. 그.. 백준 22221 - Table 1 https://www.acmicpc.net/problem/22221 이런 형태의 문제를 처음 보면 이해하기 어려울 수 있지만 다음과 같이 정리할 수 있다. 1. 숫자를 붙여 N자리 숫자를 만들어야 한다. 2. 각 행(좌에서 우로), 열(위에서 아래로), 그리고 주 대각선을 대상으로 숫자를 이어붙인다. 3. 이렇게 이어붙인 수들은 서로 중복되지 않으며 M의 배수를 만족해야 한다. 4. 0으로 시작하는 수가 있으면 안 된다. 추가로 Table 1에는 점수가 2점 이하라는 조건이 붙는다. 이는 제한에서 다음과 같은 구문을 확인할 수 있다. Otherwise your score for the test case is calculated from the formula: N. N으로 점수를 매긴다는 뜻이다. 따라.. [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.. 이전 1 2 다음
