목록2024/09 (49)
미소를뿌리는감자의 코딩
1. 문제https://www.acmicpc.net/problem/9663 2. 접근 방법 체스판에서, 대각선으로 겹치는 지 유무를 확인하기 위해, x y값들 더한 것과, x y 값을 뺀 것을 list로 만들어서 확인해 두려고 한다. 또한 y 축으로 겹치는 것을 확인하기 위해서의 리스트도 하나 만들어 두려고 한다.minus라는 list를 만들면서, 음수의 값이 들어갈 수도 있지 않을까 라고 생각을 하였지만, y-x로 빼게 된다면 음수의 값은 들어가지 않는다.- 처음에 음수값이 들어갈 것을 염려해, defaultdict 로 구현을 했었었다. 탈출 조건은 y축이 조건을 만족하면서 4에 도달했을 때이다.4에 도달하게 되면 count + 1을 해주고, return 을 해주어 마무리를 해준다. queen을 놓을..
1. 문제https://www.acmicpc.net/problem/1914 2. 접근 방법 만약, 3개의 하노이 탑을 옮긴다고 생각했을 떄, 2개의 탑을 우선, 중간 단계로 이동 시키고, 마지막 base를 마지막 막대기로 이동시키고, 다시 중간 단계 2개의 탑을 마지막 단계로 이동시킨다고 생각하면 쉽다. 중간 막대로 2개의 탑을 옮기는 것과 마지막 막대로 2개의 탑을 옮기는 것은 같은 과정이다. 단지, 막대기 위치만 다를 뿐이다. 이렇게 알게 된 3개의 탑을 옮기는 방법을 이용해서, 3개의 탑을 중간 막대기로 옮기고, base를 맨 마지막 막대기로 옮기고, 중간 막대기에 있던 3개의 탑을 마지막 막대로 옮기면 된다. 즉, n개의 탑의 이동 공식을 이용해서 n+1개의 탑의 이동 공식을 유도할 수 있는 것..
1. 문제https://www.acmicpc.net/problem/10971 2. 접근 방법예를 들어, 3개의 도시가 있다고 가정하자.3개의 도시는 0번, 1번, 2번 이라는 이름이 있다고 할 것이다. 그렇다면 도시를 방문하는 순서의 경우의 수는 몇이 될 것인가? 3! 이다. 0 - 1 - 2 - 00 - 2 - 1 - 0 1 - 0 - 2 - 11 - 2 - 0 - 1 2 - 0 - 1 - 22 - 1 - 0 -2 이렇게 될 것이다. 반면, 다음과 같은 경우는 동일한 경우에 해당된다.어떤 도시로부터 시작하냐의 차이일 뿐, 같은 cost를 지불하게 된다. 따라서, 이런 이동 경로의 경우의 수를 판단해서, cost 들을 계산해 주고, 최솟값을 반환하면 될 것이다. def make_possibilities(..
1. 개요https://www.acmicpc.net/problem/9020 2. 접근 방법만약, 10이라는 짝수가 주어졌다고 가정해 보자. 그렇다면, 생성될 수 있는 possibilities는 다음과 같다. 2 + 8 = 103 + 7 = 104 + 6 = 105 + 5 = 106 + 4 = 107 + 3 = 108 + 2 = 10 이 가능할 것이다.그 중, 2-88-2는 동일한 값이므로, 하나만 계산해 주면 된다. 5 + 5까지만 possibilities로 두면 되는 것이다. 따라서, n/2 + 1 까지만, 값을 비교하면 된다. 따라서, 2-8, 3-7, 4-6, 5-5에 대해서 두 수가 모두 소수인지 판단을 한 후, 소수라는 판단이 된다면 그 차를 두 수와 포함해서 리스트로 리스트에 저장해 둔다. [..