코드트리 - 최적의 십자 모양 폭발 # 접근 방법 완전 탐색을 활용한 시뮬레이션 문제이다. 0, 0부터 N-1, N-1까지 모든 폭탄을 터트린 후, 조건에 맞는지 검사해주면 된다. 항상 느끼는 것이지만, 모든 문제를 풀 때 각 기능을 함수로 나누는 것이 디버깅에도 유리하고 코드를 읽을 때도 잘 읽히는 것 같다. bomb함수 폭탄을 터트리며 터진 곳을 저장해주었다. 시작 위치는 height에 우선적 저장을 해주었는데, 1칸만 터지는 경우 세로로만 복사해주면 되기 때문이다. 시간을 가장 많이 소비한 곳은 폭탄을 터트린 후 격자에 중력을 작용시키는 부분이었다. gravity 함수 가로로 터지는 부분은 최대 1칸이므로 터진 곳을 저장 세로로 터지는 곳은 저장 후 정렬을 통하여 가장 위의 칸과 가장 아래 칸을 변..

코드트리 - 최단 Run Length 인코딩 # 접근 방법 문자열을 비손실 압축 방식으로, 오른쪽으로 shift를 통하여 최소 길이로 만드는 문제이다. 평소에 많이 접해보지 않은 문제이지만 아이디어를 떠올리는 것이 어렵지 않았다. 오른쪽 shift를 통해서 현재보다 짧은 길이로 만들기 위해서는, 가장 먼저 나온 문자열과 가장 마지막에 나온 문자열이 같아야 된다. 우선, 주어진 문자열을 순회하며 비손실 압축을 해준다. 이후 길이가 2인 경우 => 모든 문자열이 1개로 이루어진 경우는 바로 2를 출력해준다. 그렇지 않다면, 뒤에서 2번째 문자와 가장 첫 문자를 비교해준 후, 같다면 개수를 합쳐준다. import sys input = sys.stdin.readline words = input().strip()..

백준 1948 - 임계경로 시간 제한 2초, 메모리 제한 512MB # 조건 월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다. 어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라. 출발 도시는..

백준 20183 - 골목 대장 호석 - 효율성2 시간 제한 5초, 메모리 제한 512MB # 조건 소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다. 교차로의 번호는 1번부터 N 번까지로 표현한다. 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사람에게 수금할 것이다. 수금하는 요금은 골목마다 다를 수 있다. 당신은 A 번 교차로에서 B 번 교차로까지 C 원을 가지고 가려고 한다. 호석이의 횡포를 보며 짜증은 나지만, 분신술을 이겨낼 방법이 없어서 돈을 내고 가려고 한다. 하지만 이왕 지나갈 거면, 최소한의 수치심..

백준 1445 - 일요일 아침의 데이트 시간 제한 2초, 메모리 제한 128MB # 조건 일요일 아침에 형택이는 Maroon5의 Sunday Morning이란 노래를 들으면서 여자친구와의 로맨틱한 여행을 떠나기로 했다. 형택이는 이것저것 환상에 빠져있다가, 계획을 세우는데 실패했다. 따라서, 주위에 있는 숲을 같이 탐험하기로 했다. 깊은 숲속에는 정말 아름다운 꽃이 하나있다. 형택이는 여자친구의 마음을 감동시키기 위해서, 꽃을 보여주면서 자신의 마음을 전해주려고 급하게 계획했다. 불행하게도, 사람들이 숲에다 쓰레기를 버려서 형택이의 계획은 정말 망가지기 직전이다. 형택이는 그동안 여자친구와 사귀면서 2가지 깨달은 것이 있는데, 한 가지는 쓰레기를 통과해서 지나가는 것을 정말 싫어하는 것이고, 쓰레기를 따..

백준 22857 - 가장 긴 짝수 연속한 부분 수열(small) 시간 제한 1초, 메모리 제한 1024MB # 조건 길이가 $N$인 수열 $S$가 있다. 수열 $S$는 1 이상인 정수로 이루어져 있다. 수열 $S$에서 원하는 위치에 있는 수를 골라 최대 $K$번 삭제를 할 수 있다. 예를 들어, 수열 $S$가 다음과 같이 구성되어 있다고 가정하자. 수열 S : 1 2 3 4 5 6 7 8 수열 $S$에서 4번째에 있는 4를 지운다고 하면 아래와 같다. 수열 S : 1 2 3 5 6 7 8 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자. 입력 수열 S의 길이 N와 삭제할 수 있는 최대 횟수인 K가 공백으로 구분되어 주어진다. 두 번..

백준 1240 - 노드사이의 거리 시간 제한 2초, 메모리 제한 128MB # 조건 N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 입력 첫째 줄에 노드의 개수 N과 거리를 알고 싶은 노드 쌍의 개수 M이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍이 한 줄에 한 쌍씩 입력된다. 출력 M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다. 제한 $2≤N≤1,000$ $1≤M≤1,000$ 트리 상에 연결된 두 점과 거리는 $10,000$ 이하인 자연수이다. 트리 노드의 번호는 $1$부터 $N$까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다. #..

백준 2553 - 마지막 팩토리얼 수 시간 제한 0.3초(추가 시간 없음), 메모리 제한 128MB # 조건 N!의 값을 계산한 후에, 0이 아닌 가장 낮은 자리 수를 구하시오. 예를 들어, 4! = 24이기 때문에, 0이 아닌 가장 낮은 자리 수는 4이다. 또, 5!은 120이기 때문에, 0이 아닌 가장 낮은 자리 수는 2이다. 입력 첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 N!의 0이 아닌 마지막 자리수를 출력한다. # 접근 방법 N!을 math.factorial 또는 반복문을 통하여 구해준다. 이후 문자열로 변경하여 뒤에서부터 탐색하며 0이 아닌 값을 출력하고 종료해준다. import sys sys.stdin = open('input.txt&#..

백준 1158_요세푸스 문제 시간 제한 2초, 메모리 제한 256MB # 조건 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(