문제 https://www.acmicpc.net/problem/27453 27453번: 귀엽기만 한 게 아닌 한별 양 첫 번째 줄에 마을의 세로 크기 $N$, 가로 크기 $M$, 한별이가 연속해서 막을 수 있는 불상사의 개수 $K$가 주어진다. ($2\leq N,M\leq 1\,000$, $0\leq K\leq 27$) 다음 $N$ 개의 줄에 걸쳐 마을의 상태가 주어진 www.acmicpc.net 풀이 지나온 3칸의 불상사 합과 이전에 들렀던 칸은 이동할 수 없다는 것을 생각해서 구현해야 하는 문제 갈 수 없는 곳의 조건 설정을 잘해야 한다. 내가 설정한 갈 수 있는 조건은 다음과 같다. 벽("X")이 아닌 경우 이전에 방문했던 곳(item)이 아닌 경우 방문하지 않았거나(-1) 해당 구역의 불상사가 다..
문제 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 풀이 괄호를 잘해서 가장 높은 값을 만드는 문제 짝수인 인덱스에는 숫자가 들어가고 홀수인 인덱스에는 연산 기호가 들어간다. 평범하게 계산한 경우와 괄호를 친 경우를 통해 결과를 찾아낸다. 위의 경우를 생각해 내기가 많이 까다로웠다. 제출 코드 # 2023/02/12 BruteForce # https://www.acmicpc.net/problem/16637 import sys ..
문제 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이 늑대와 양의 수를 구하는 BFS문제 한 공간에 양이 더 많으면 늑대의 수는 0이 되고, 늑대가 더 많거나 같은 경우는 양들의 수는 0이 된다. 전 지역을 탐색할 때 벽이 아닌 경우, 해당 공간에서 움직일 수 있는 모든 구역을 조사한 뒤 양의 수와 늑대의 수를 비교해서 정답을 구한다. 제출 코드 # 2023/02/10 BFS # https://www.acmicpc.net/pr..
문제 https://www.acmicpc.net/problem/25916 25916번: 싫은데요 $6$번째 구멍부터 $8$번째 구멍까지 막으면 총 $9$의 부피를 소모하고, 최대값인 $9$를 출력한다 www.acmicpc.net 풀이 햄스터가 막을 수 있는 최대 크기를 출력하는 문제 두 포인터로 맨 처음부터 끝까지 탐색을 해본다. 부피가 부족하면 end + 1, 최대로 막을 수 있는 부피를 넘으면 start + 1을 하여 end가 N과 같아질 때까지 탐색한다. 제출 코드 # 2023/02/09 두 포인터 # https://www.acmicpc.net/problem/25916 import sys input = sys.stdin.readline # 두 포인터를 이용한다. def search(): res = ..
문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이 모든 경우를 탐색하는 bruteforce 문제 특정 높이에 따른 결과가 어떤지 비교하여 최소 시간과 그중 가장 높은 블록의 높이를 출력한다. 블록을 부술 때 인벤토리에 블록이 들어온다는 점을 잘 생각해야 한다. 제출 코드 # 2023/02/08 bruteforce # https://www.acmicpc.net/problem/18111 import sys input = sys.stdin..
문제 https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 meet in th middle 알고리즘과 이진 탐색을 이용하여 풀어야 하는 문제 처음에 배열을 두 개로 분리한 뒤 왼쪽의 부분 집합과 오른쪽의 부분 집합의 합을 이용해 정답을 구하는 문제이다. 배얼을 두개로 분리한 이유는 길이가 40인 배열의 완전 탐색은 2^40번을 탐색해야 한다. 그러나, 반반으로 나누면 2^20 * 2이므로 확실히 드는 시간이 줄어듦을 알 수 있다. 제출 코드 #..
문제 https://www.acmicpc.net/problem/18232 18232번: 텔레포트 정거장 첫 번째 줄에 정수 N, M이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 300,000, 0 ≤ M ≤ min(N×(N-1)/2, 300,000)) 두 번째 줄에 정수 S, E가 공백으로 구분되어 주어진다. (1 ≤ S, E ≤ N, S ≠ E) 그 다음 줄부터 M www.acmicpc.net 풀이 단순한 BFS 문제 특정 구역에 텔레포트를 할 수 있는 구역을 설정한 뒤 해당 구역을 방문하면 텔레포트를 할 수 있게 하면 된다. 유의해야 할 점은 한 공간에 여러 곳을 텔레포트할 수도 있다는 것과, 텔레포트는 일방통행이 아닌 양방통행이라는 것이다. 이 코드같은 경우는 딕셔너리 안에 키는 장소, 값은 se..
문제 https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net 풀이 단순한 BFS 문제 나이트의 초기 위치부터 모든 위치를 탐색한 뒤, 저장해 두었던 상대편 말의 좌표값을 대입한 뒤 1을 빼고 출력한다. 제출 코드 # 2023/02/06 BFS # https://www.acmicpc.net/problem/18404 from collections import deque import sys input = sys.stdi..
