백준 14925 - 목장 건설하기시간 제한 1초, 메모리 제한 512MB# 조건랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다.그는 목장을 하나의 정사각형으로 최대한 크게 지으려 하는데, 그 안에 나무나 바위는 없어야 한다. 땅의 세로 길이가 M미터, 가로 길이가 N미터일 때, 1미터 간격의 격자로 된 땅의 지도를 M x N행렬로 표현하자. 이때, 행렬의 원소 0은 들판, 1은 나무 그리고 2는 돌을 의미한다. 랜드씨의 땅에서 지을 수 있는 가장 큰 정사각형 목장의 한 변의 크기 L을 출력하시오.# 접근 방법DP를 이용하여 풀어준다.records 테이블은 M행 N열을 오른쪽 아래 ..

백준 18427 - 함께 블록 쌓기시간 제한 1초, 메모리 제한 256MB# 조건1번부터 N번까지의 학생들은 각각 블록들을 가지고 있다. 학생마다 최대 M개의 블록을 가지고 있을 수 있으며, 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르다. 이 때 1번부터 N번까지의 학생들이 가진 블록을 차례대로 사용하여 바닥에서부터 쌓아올려 하나의 탑을 만들고자 한다.단, 어떤 학생의 블록은 사용하지 않아도 되며 한 학생당 최대 1개의 블록만을 사용할 수 있다.1번부터 N번까지의 학생들이 가지고 있는 블록들에 대한 정보가 주어졌을 때, 높이가 정확히 H인 탑을 만들 수 있는 경우의 수를 계산하는 프로그램을 작성하시오.예를 들어 N=3, M=3, H=5일 때, 각 학생마다 가지고 있는 블록들의 높이가 다음..

백준 1535 - 안녕시간 제한 2초, 메모리 제한 128MB# 조건세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 프로그램을 작성하시오.입력..

백준 15681 - 트리와 쿼리시간 제한 1초, 메모리 제한 128MB# 조건간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.입력트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105)이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)이는 U와 V를 양 끝점으로 하는 간선이 트리에 속함을 의미한다.이어 Q줄에 걸쳐, 문제에 설명한 U가 하나씩 주어진다. (1 ≤ U ≤ N)입력으로 주어지는 트리는 항상 올바른 트리임이 보장된다.출력Q줄에 걸쳐 각 쿼리의..

백준 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 는 수열 ..