목록백준/구현, 수학 (3)
Do Something
벡터 매칭 성공 문제 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다. 벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다. 평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다. 테스트 케이스의 첫째 줄에 점의 개수 N이 주어진다. N은 짝수이다. 둘째 줄부터 N개의 줄에 점의 좌표가 주어진다. N은 20보다 작거나 같은 자연수이고, 좌표는 절댓값..
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 머리좀 식힐라고 간만에 실버문제를 풀었다. 하노이의 탑 진짜 너무 오랫만에 봐서 기억은 안났고 생각해내야 했다. 우선 천천히 하노이의 탑을 쌓아보았다. ㅋㅋㅋㅋ진짜 이러고 있었음 3짜리 두번정도 쌓아보니까 나온 점화식은 다음과 같다..
이왜맞? 을 한 문제였다. 현재 상태를 만들 수 있는 격자판을 만드는 문제이다. 반대로 뒤집어서 생각하면 현재 상태에서 새로 만들 수 있는 상태를 찾아내는 문제이다. 따라서 현재 상태를 바꿀 수 있는 경우를 모두 고르면 된다. 우선 위 예시를 보면 W B B B 이라는 상태인인데, w를 누르는 순간 모든 격자가 B로 통일되버리니 누를 수 없다. (다시 복구할 수 없기 때문) [0,1]의 B버튼을 눌러도 W랑 통합이 되어버리고, [1,0]도 마찬가지이다. 오직 오른쪽 아래 [1,1] B버튼만이 누를 수 있다. 즉, 양옆에 다른 색이 붙어있다면 해당 색과 통일되어 버려서 누를 수 없다. 모든 붙어있는 면이 같은색이면 누를 수 있다. 그리고 나는 문제를 풀 때 이 예시를 생각했다. W W W W W W B W..