2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 2차원 리스트를 활용한 간단한 문제. 아이디어 언뜻 보기에 귀찮은 문제라고 느껴질 수 있다. 근데 문제에서 제공된 범위가 100 100이라는 매우 작은 범위이다. 이런 경우는 모든 좌표를 2차윈 리스트로 간단하게 해결 가능하다. 먼저 100 * 100 의 이차원 리스트에서 값을 전부 False로 선언해 준다. 그리고 각 색종이가 있는 영역의 좌표들을 True로 바꿔주고 마지막으로 True의 개수를 세어서 출력해주면 된다. 전체 코드 N = int(input()) paper..
7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 냅색 응용문제. 아이디어 냅색 알고리즘의 기본 원리를 이용해 해결할 수 있다. 이차원 리스트 backpack[x][y]는 x번째 앱까지 y비용으로 얻을 수 있는 최대 메모리값이다. 1. 열의 크기는 제시된 모든 비용의 총합으로 한다. 2 - 1. 현재 앱의 비용 costList [i]가 j보다 크면 그대로 둔다. backpack[i][j] = backpack[i - 1][j] 2 - 2. j 가 더 크면 현재 앱의 유무를 비교해 값을 업데이트해준다. backpack[i..
4179번: 불!입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자www.acmicpc.net 반나절 삽질한 BFS문제. 문제가 어렵게 느껴지진 않았는데 시간초과, 메모리초과 등등 오답파티가 됐다.아이디어- 문제에서 탈출 조건이 가장자리에 접한 공간에서 탈출할 수 있다고 한다. 이 말은 지훈이가 가장자리에 도착만 하면 자동으로 탈출 가능하다. - 순서는 지훈이가 한번 이동하고 나서 불이 확산되고 1초가 지난다. - 만약 지훈이가 이동한 후 위치에 불이 번진다면 그곳은 못 가는 위치이다. - 이 문제를 해결하려면 지훈과 불 각각의 큐를 만들어서..
2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 해석을 잘해야 하는 문제. 아이디어 먼저 문제가 요구하는 것을 이해하는 게 필요하다. 문제에서는 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하라고 했다. 이는 아래 예제를 보며 설명해 보면, 이런 식으로 각 센서들을 커버할 수 있는 최소 영역의 크기를 구하면 된다. 그림을 보면 알다시피 문제의 답을 구할 때 센서의 위치는 겹쳐도 상관없다. 문제를 해결하려면, 센서들의 거리가 가장 먼 곳부터 차례대로 지워주면 된다. 예를 들..
16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net BFS느낌의 구현 문제 아이디어 폭탄을 추가하고 터트리는 과정에서 큐를 사용하면 편할 거 같아 deque를 사용했다. 1초마다 어떻게 격자판의 변하는지 생각하며 코드를 작성했다. 전체 코드 from collections import deque dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] grid = [] # 격자판 boomList = deque() # 폭탄 좌표 리스트 R, C, N = map(int, input().split()) for i in range..
1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 활용한 최소 시간을 구하는 문제. 아이디어 현재 위치(x)에서 갈 수 있는 거리는 x - 1, x + 1, x * 2이다. 각 경우마다 if문을 통해 조건을 확인해준다. 이전에 방문하지 않은 위치라면 그 위치까지 걸리는 시간들을 BFS방식으로 순회하며 시간을 저장해준다. 전체 코드 from collections import deque N, K = map(int, input().split()) deq = deque() deq.a..
15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제 아이디어 어차피 같은 숫자를 반복해서 사용해도 되므로, 문제에서 제공한 N개의 수에서 중복을 제거해 준다. 백트래킹을 활용해 문제를 해결하면 된다. 전체 코드 N, M = map(int, input().split()) numList = [int(x) for x in input().split()] numList = sorted(list(set(numList))) # 중복 제거후 정렬 n = len(numList) answer = list() seq..
14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 지도에서 모든 지점의 최단거리를 구하는 문제. 아이디어 BFS를 사용했다. 지도에서 최단거리 == BFS 거의 공식처럼 머리에서 나온다... 문제를 해결하기 위해 목표 지점(2로 표시)과 갈 수 없는 땅(0으로 표시)의 좌표는 따로 저장해 둔다. 전체 코드 from collections import deque dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] start_x, start_y = 0, 0 ..
