목록코딩 테스트 (186)
미소를뿌리는감자의 코딩
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에 대해서 두 수가 모두 소수인지 판단을 한 후, 소수라는 판단이 된다면 그 차를 두 수와 포함해서 리스트로 리스트에 저장해 둔다. [..
1. 문제https://www.acmicpc.net/problem/1978 2. 접근 방법어렴풋이 기억하기로, 소수의 경우 루트를 씌운 값까지 나누어 보고, 나누어 떨어지지 않는다면 소수인 것으로 판별될 수 있음이 기억났다. 따라서 이를 적용해 보는 코드를 작성하였다.또한 루트를 씌우기에, 나머지가 생기기 마련이다. 따라서 이를 int()로 감싸서, 나머지를 절삭해 주었다.또한 +1을 해주어 절삭될 수 있는 값에 대한 처리도 포함하도록 하였다. - '에라토스테네스의 체' 라는 개념이었다.3. 코드import mathdef find_decimal(n): if n == 1: return 0 for i in range(2, int(math.sqrt(n)) + 1): if n..