백준 5972 - 택배 배송시간 제한 1초, 메모리 제한 128MB# 조건농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.농부 현서에게는 지도가 있습니다. N (1 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 다음 지도를 참고하세요. [2]--- / | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | / /1 [4]---..

백준 7562 - 나이트의 이동시간 제한 1초, 메모리 제한 256MB# 조건체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?# 접근 방법BFS를 이용해서 풀어주면 된다.다만, 상하좌우가 아닌 해당 칸들 만큼 이동하도록 방향 벡터를 잘 설정 해주면 된다.import sys sys.stdin = open('input.txt') input = sys.stdin.readline from collections import deque def bfs(bi, bj, goal_i, goal_j): q = deque() q.append((bi, bj..

백준 1926 - 그림시간 제한 2초, 메모리 제한 128MB# 조건어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라.단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.# 접근 방법전형적인 그래프 탐색 문제이다.코테 대비를 하다보면 자주 만나는 영역의 개수 구하기와 동일한 문제이다.BFS로 해당 그룹의 개수를 카운트 해주고 max_size를 갱신해 나가면 된다.import syssys.stdin = open('input.txt')input = sys.stdin.readlinefrom collec..

백준 10974 - 모든 순열시간 제한 1초, 메모리 제한 256MB# 조건N이 주어졌을 떄, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.입력첫째 줄에 N(1출력첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.# 접근 방법permutations 사용하여 풀어주면 된다.import syssys.stdin = open('input.txt')input = sys.stdin.readlinefrom itertools import permutationsN = int(input())nums = [i for i in range(1, N+1)]for comb in permutations(nums, N): print(*comb)

백준 17390 - 이건 꼭 풀어야 해!시간 제한 1초, 메모리 제한 512MB# 조건숭실골 높은 언덕 깊은 골짜기에 출제로 고통 받는 욱제가 살고 있다!욱제는 또 출제를 해야 해서 단단히 화가 났다. 그래서 욱제는 길이 N짜리 수열 A를 만들고, A를 비내림차순으로 정렬해서 수열 B를 만들어 버렸다!! 여기서 B를 출력하기만 하면 문제가 너무 쉬우니까 하나만 더 하자. 아래와 같은 질문이 무려 Q개나 주어진다!!L R: BL + BL+1 + ... + BR-1 + BR 을 출력한다.입력첫 번째 줄에 수열 A의 길이 N과 질문의 개수 Q가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 300,000)두 번째 줄에 N개의 정수 A1, A2, ..., AN 이 공백으로 구분되어 주어진다. Ai 는 수열 ..

백준 30804 - 과일 탕후루시간 제한 2초, 메모리 제한 1024MB# 조건은하는 긴 막대에 $N$개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 $1$부터 $9$까지의 번호가 붙어있고, 앞쪽부터 차례로 $S_1, S_2, \cdots, S_N$번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 $a$개, 뒤에서 $b$개의 과일을 빼면 $S_{a+1}, S_{a+2}, \cdots, S_{N-b-1}, S_{N-b}$번 과일, 총 $N-(a+b)$개가 꽂혀있는 탕후..

백준 10711 - 모래성시간 제한 1초, 메모리 제한 256MB# 조건명우가 만든 모래성을 2차원 격자단위로 만들었으며, 각 격자마다 튼튼함의 정도를 다르게 해서 성을 만들었다. 이 튼튼함은 1부터 9 사이의 숫자로 표현될 수 있다. 이 튼튼함은, 자기 격자 주변의 8방향 (위 아래 왼쪽 오른쪽, 그리고 대각선) 을 봐서 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너질 수 있음을 의미한다. 그 이외의 경우는 파도가 쳐도 무너지지 않는다. 모래성이 무너진 경우, 그 격자는 모래성이 쌓여있지 않은 것으로 취급한다.이 모래성은 언젠가는 파도에 의해서 깎이고 깎여서, 결국 한가지 형태로 수렴할 것이다. 모래성을 완성한 명우는 문득 자신이 만든 예술품의 수명..

백준 2824 - 최대공약수시간 제한 1초, 메모리 제한 192MB# 조건상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다.셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이..

백준 15655 - N과 M(6)시간 제한 1초, 메모리 제한 512MB# 조건N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열고른 수열은 오름차순이어야 한다.입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.# 접근 방법전형적인 백트래킹 문제이다.조합을 사용하여 ..