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..
문제 링크스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게 된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다.문제에 제시된 조건과 요구 결과이다. 최대 점수를 얻을 수 있도록 스티커를 떼야한다. 처음엔 공유하는 스티커가 찢어져 사용할 수 없으니 BFS인가..? 했는데 전혀 아니었고, 그럼 그리디인가..? 했는데 무조건 높은 점수를 더해가면 나중에 틀리는 반례가 있었다. 즉, 모든 스티커에 방문할 때마다 최댓값을 비교하며 변경해야 하는 다이내믹 프로그래밍이었다. 예시를 통해 그리디가 아닌 이유를 알 수 있다...
https://www.acmicpc.net/problem/3085 3085번: 사탕 게임예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.www.acmicpc.net 인접한 두 사탕의 색깔이 다르면 스왑한 뒤 전체 사탕의 색깔을 탐색하면서 하나의 색으로 일치하는 가장 긴 행 or 열을 찾으면 된다. 처음에 스왑하고 유지되는 줄 알았는데, 탐색 후에 다시 원래 상태로 되돌려놔야 한다.- 상하좌우로 탐색- 어? 나랑 붙어있는데 색깔이 다르네?- 스왑 후 N x N 탐색하면서 색깔이 연속하는 가장 긴 행 or 열을 찾기- 탐색 끝나면 다시 재스왑 (원래대로 돌려놓기)- 다시 색깔 다른 인접한 칸 찾기- 반복 1. origin에 기존 색깔을 저장해 두고, 인접한 사탕의 색깔이 다르면 스..
https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 일단 이 문제는 1080번 행렬 문제와 비슷하다. 문제에서 최소 횟수를 요구하고 있기 때문에 한 번 바꿔준 애는 다시 바꿔주면 안 되겠다는 생각이 들었다. 현재 전구 상태가 원하는 전구 상태와 같으면 그냥 넘어가고, 아니면 눌러주는 방식으로 구현하고자 했다. 하지만 이렇게 풀면 예제를 틀린다. 예제에서는 000을 010으로 바꾸고 싶어 하는데, 내가 말한 대로 풀게 되..
