안녕

0. 문제 링크 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 1. 풀이 방법 큐를 4개 사용했음. (백조가 움직이는 큐, 물이 녹는 큐, 다음 턴에 백조가 움직여야 하는 큐, 다음 턴에 물이 녹아야 하는 큐) 사실 이것만 있어도 충분히 풀 수 있을거라 생각함 2. 코드 import sys from collections import deque input = sys.stdin.readline def waterMelt..

0. 문제 링크 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1. 풀이 방법 이 문제는 DFS + DP이다. 안 그래도 어려운 두 개를 붙였으니 더 어려웠던 것 같다. https://minny27.tistory.com/42 [백준 1937] 욕심쟁이 판다 (Python) 문제 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤..

0. 문제 링크 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 1. 풀이 방법 굉장히 찝찝하게 풀었다. 정렬을 이용해서 풀었는데, 파이썬은 문자열을 길이가 아닌 사전 순대로 나열해서 정렬을 해준다. 그래서 정렬을 해서 직전 문자열이 다음 문자열의 부분이 되는가만 파악하면 된다. 나는 좀 거창한 풀이를 생각했는데, 생각보다 간단해서 허무했다. 사실 숫자의 트리를 만들어서 풀려고 했다. 예를 들어 911 다음에 91112..

0. 문제 링크 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 풀이 방법 이 문제는 감이 중요할 것 같은 문제이다. 행렬의 곱셈 연산에서 생각했을 때, DP로 풀어야 될 것 같지만 정답은 그리디로 풀어야 하는 문제이다. 아래의 코드에서 써놓았는데, i < j < k라고 가정했을 때, 최소 연산은 당연히도 (i + j) + (i + j + k) = 2 * (i + j) + k이다. i + k를 먼저 수행한다면, 2 * (i ..

0. 문제 링크 https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 1. 풀이 방법 일단 맨 처음에는 BFS로 문제를 풀었는데, 시간 초과, 메모리 초과가 발생하였다. BFS가 아님을 깨달았고, 고등학교의 확통에서 비슷한 문제를 풀었던 경험이 생각났다. 현재 위치로 올 수 있는 애는 내 좌측과 위이므로, 좌측과 위로 갈 수 있는 경우의 수를 더하면 현재 위치에 도달할 수 있다.는 것이 확통에서 문제를 푼 방법이다. 물론 조합을 사용..

0. 문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. 풀이 방법 내 기준 가장 신박했던 문제 문제 유형은 이분 탐색 + 매개 변수 탐색이다. 이 유형은 최적화 문제를 결정 문제로 바꿔서 푸는 문제이다. 그렇다면 어떤 부분이 최적화일까? 를 먼저 생각해야 하는데, 문제에 나와있듯이 가장 인접한 두 공유기 사이의 '최대 거리'이다. 그러면 이 부분을 결정 문제로 바꿔야 하는데, ..

0. 문제 링크 https://www.acmicpc.net/problem/21925 21925번: 짝수 팰린드롬 (1, 1), (5, 6, 7, 7, 6, 5), (5, 5) www.acmicpc.net 1. 풀이 방법 스택이 비어있다면, 매 숫자마다 스택에 넣는다. 그리고 다음 숫자로 이동한다. 만약에 스택에 숫자가 들어가 있다면, 스택의 길이를 측정한다 -> l 현재 숫자의 위치인 cur과 스택의 마지막 숫자를 비교하며 좌우로 넓혀가며 팰린드롬을 만족하는지 확인한다. 이때 스택의 길이가 남은 숫자의 길이보다 길다면 이 또한 팰린드롬을 만들 수 없다. 만약 스택에 들어있는 숫자 3개와 현재 숫자의 위치인 cur에서 cur + 2까지의 3개의 숫자가 팰린드롬을 만족한다면, 스택을 모두 비운다. 그리고 T..

0. 문제 링크 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 1. 풀이 방법 4개씩 투포인터로 범위를 잡는다. set으로 만든 후에, 중복되지 않는 개수를 센다. 만약 행사로 주는 쿠폰에 해당하는 번호가 없으면, 1을 더해서 개수를 센다. 마지막으로 '회전 초밥' 이므로, 맨 뒤에서 맨 앞까지 먹는 경우도 계산해야 한다. 해당 코드는 매우 느리다. 최적화 작업은 하지 않았다. 통과는 된다. 아래는 내가..

0. 문제 링크 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 1. 풀이 방법 중복 제거를 위하여 세트로 정렬한다. 각 번호의 인덱스가 압축된 좌표의 번호가 된다. 그대로 출력하면 끝 2. 코드 import sys input = sys.stdin.readline if __name__ == "__main__": n = int(input()) maps = list(map(int, input().s..

0. 문제 링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 1. 풀이 방법 0으로 끝나는 숫자와 1로 끝나는 숫자를 구분한다. i 자리의 숫자는 i - 1 번째 어떤 숫자든 0을 붙여도 상관없다. i 자리의 숫자는 i - 1 번째 숫자에서 끝이 0으로 끝나는 숫자에만 1을 붙일 수 있다. 이런 점화식을 세운 후 문제를 풀면 끝 조금 더 최적화를 위해서 메모리를 2*2만 사용하였다. 실제 메모리 사용은 줄어들지 않았는데, 이유는 ..