https://www.acmicpc.net/problem/15686정답 코드는 맨 밑에 있습니다! 음 그래프네. BFS로 풀면 되나?근데 집집마다 치킨 거리가 다르네...게다가 어떤 치킨집을 없애느냐에 따라 나뉘네...가까운 치킨 집을 지울 때가 정답일 때도 있네..?심지어 M이 13 이하네..?이건 완탐이다...라는 의식의 흐름으로 문제를 풀려고 했다. 근데 잘 안 풀린다.. 처음 풀었을 때 틀린 코드 두 번 풀었을 때 틀린 코드import sysfrom collections import defaultdictinput = sys.stdin.readlinedef find_neareat_distance(houses, chicken_houses): answer = 0 for house in h..
https://www.acmicpc.net/problem/14889 DFS로 풀었다. 이 문제를 딱 보자마자 모든 경우를 고려해야겠다고 판단했지만, 어떻게 코드를 구현해야 할지 몰랐다... 한 시간 정도 고민한 거 같다.처음에는 인원을 짝지어서 넣고 바로 시너지를 계산해 줘야 되나 고민했는데 너무 복잡해지고 코드도 모르겠어서 다른 방법을 생각하려고 했다. 문제 풀이먼저 스타트팀과 링크팀의 인원이 같아질 때까지 선수를 넣는다. (이때 모든 경우를 고려하는 거다. 트리 형식으로 스타트팀과 링크팀에 넣어주었다.)그리고 스타트팀과 링크팀의 인원 수가 같아지면 각 팀의 시너지를 비교했다.이 시너지가 최소인 경우를 찾고자 했다. (DFS로 반복) 정답 코드import sysinput = sys.stdin.readl..
https://www.acmicpc.net/problem/14888 연산자가 어떻게 들어가느냐에 따라 값이 완전히 바뀌기 때문에 DFS를 활용하여 모든 결괏값을 비교하도록 하였다. 이때 중요한 것은 한 번 사용한 연산자는 -1을 해주어야 한다. 그리고 depth == n 일 때는 결과를 비교하고 나와야 한다. 그리고....if else가 아니라 if 분기문으로 사용하기 때문에 반드시 메서드 인자에서 연산을 해야 한다. 처음에 연산값을 변수에 담은 후 dfs 메서드 인자로 넣었는데 그러면 답이 제대로 안 나온다. 확인해 보니 여러 분기문이 돌아가는 과정에서 계산값이 계속 바뀌어서 그렇다고 한다.. 이렇게 작성하면 안 되고, 이렇게 작성해야 한다. 정답 코드import sysinput = sys.stdin..
https://www.acmicpc.net/problem/14501 보자마자 DP인건 알아챘는데 점화식 세우는데 오래 걸렸다..문제 예제를 보면 6, 7일 같은 경우 N을 벗어나기 때문에 포함시킬 수 없다. 이 조건을 보고 역순으로 풀어야겠다고 판단했다. (근데 앞에서부터 풀어도 된다.) 뒤에서부터 오는데 만약 인덱스 + time이 N을 넘어가면 dp[i] = dp[i+1]을 해주었다.처음에는 dp[i] = 0을 했는데, 이렇게 되면 time이 1일 때도 0으로 되기 때문에 틀린다. ex) n = 7일 때,만약 6일에 하는 미팅이 이틀 걸리면 퇴사 날짜를 넘기기 때문에 못한다. 근데 7일에 하는 미팅이 하루 걸리는 거면 포함시켜야 한다. 이를 포함시키는 코드가 아래와 같다.이 코드를 처음에는 dp[i] ..
https://www.acmicpc.net/problem/13458 먼저 를 해주고,남은 시험장 인원수가 부감독관이 맡을 수 있는 인원보다 많으면while 루프문을 돌려 를 해주었다. 근데 이렇게 풀면 틀린다... 문제에 이 예제가 있을 때부터 쎄하긴 했는데 역시나 바로 시간초과에 당첨되었다.이유는, 시험장 인원수가 너무 많을 경우 빼주는 while문이 많이 돌아가서 많은 시간이 소요되기 때문이다즉, 한 번씩 빼주는게 아니라 부감독관이 맡을 수 있는 인원수를 수학적으로 계산해서 처리해야 한다. 이때 필요한게 나눗셈이다. 기존 코드는 아래와 같다. 총감독관이 맡을 수 있는 인원수를 먼저 빼주고 부감독관이 맡을 수 있는 인원수를 while문으로 계속 돌려가며 빼줬는데 이렇게 하면 안 되고, 이렇게 바꿔주어야..
https://www.acmicpc.net/problem/1021 문제 풀이n == 10일 때 1부터 10까지의 숫자를 담는 numbers 덱과, 뽑고 싶은 숫자들이 담긴 wants 덱이 있다고 가정하고 풀면 된다. 먼저 numbers[0] == wants[0]일 경우, 두 덱의 첫 번째 원소를 삭제해 준다. 그게 아니라면, 다시 두 가지 분기로 나누어 생각해야 한다. 뽑고 싶은 숫자가 첫 번째 인덱스와 가까운지, 아니면 마지막 인덱스와 가까운지 고려해야 한다. 만약 첫 번째 인덱스와 가까울 경우 왼쪽으로 밀어주고, 마지막 인덱스와 가까울 경우 오른쪽으로 밀어준다. 이때 절댓값 메서드를 사용했다.왼쪽이나 오른쪽으로 미는 것은 카운트를 올려야 한다. 정답 코드import sysfrom collectio..
https://www.acmicpc.net/problem/10866 문제 풀이문제 요구사항에 맞춰서 메서드를 구현하고, 조건문으로 분기처리 하면 된다! 물론 앞뒤로 빼고 요리조리 건드리는 과정에서 시간 초과가 발생할 수 있기 때문에 반드시 파이썬의 덱 컬렉션을 써서 구현해야 한다. 덱의 경우 앞뒤로 빼고 넣을 때 O(1)의 시간복잡도를 가진다. 정답 코드import sysfrom collections import dequeinput = sys.stdin.readlinen = int(input())numbers = deque()def push_front(x): numbers.appendleft(x)def push_back(x): numbers.append(x)def pop_front(): ..
https://www.acmicpc.net/problem/2164 문제 풀이문제에 주어진 단계를 지켜가며 구현하면 된다. 이때 시간 초과가 날 수 있기 때문에 파이썬의 덱을 활용해서 O(1)으로 구현했다.맨 위의 숫자를 popleft()로 버린다. 버리기 때문에 따로 변수에 저장하지 않는다.그다음 숫자를 popleft()로 빼서 변수에 저장한 후 append()를 통해 맨 밑에 저장한다.위 과정을 덱의 크기가 1 이하가 될 때까지 반복한다. 정답 코드import sysfrom collections import dequeinput = sys.stdin.readlinen = int(input())numbers = deque()for i in range(1, n+1): numbers.append(i)w..
