본문 바로가기
728x90

Programming56

[Solved] BOJ: 2805 | 나무 자르기 문제여러 높이의 나무들이 주어지고같은 높이로 이 나무들을 잘라서 최소 M미터 이상의 나무를 확보하고자 한다.입력과 출력입력첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.출력적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.문제 해결 요약적절한 절단 높이를 탐색하면서 최소 M미터 이상의 나무를 확보해야한다.시간 복잡도를 줄이기 위해 이진.. 2022. 11. 15.
[Solved] BOJ: 4949 | 균형잡힌 세상 문제주어진 문자열에서 중괄호와 대괄호가 짝을 이뤄야 함.입력과 출력입력하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다.입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.출력각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.문제 해결 요약문자열에서 왼쪽 괄호 등장하면 스택에 오른쪽 괄호 추가문자열에서 오른쪽 괄호 등장하면 스택에서 pop한거와 비교해서 같다면 균형O 아니라면 균형X코드 설명import 및 입력받기-from collections import dequeimport sysinput = .. 2022. 11. 11.
[Solved] BOJ: 1759 | 암호 만들기 문제모음 최소 1개 이상, 자음 최소 2개 이상으로 총 l개의 단어 조합을 사전식으로 배열함입력과 출력입력첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.출력각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.문제 해결 요약입력 받은 단어들에서 자모음을 분리해 각각 자음리스트 모음리스트로 추가모음조합과 자음조합으로 단어 생성사전순 배열 및 출력코드 설명import 및 입력받기-from itertools import combinationsimport sysinput = sys.stdin.readlinel, c = map(int, input().split())l.. 2022. 11. 11.
[Solved] BOJ: 14889 | 스타트와 링크 문제N(짝수) 명의 사람들을 스타트, 링크 팀으로 나누어 배정팀에 i와 j가 소속되면 팀에 더해지는 능력치는 Sij + Sji각각의 능력치들을 합하면 팀의 능력치스타트 팀과 링크 팀의 능력치 차가 최소가 되도록 사람들을 분배하자.입력과 출력입력첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.출력첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.문제 해결 요약코드 설명import 및 입력받기-from itertools import combinationsimport sys.. 2022. 11. 11.
[Solved] BOJ: 11651 | 좌표 정렬하기 2 문제y좌표 오름차순으로 좌표 정렬y좌표가 같을 시, x 오름차순으로 좌표 정렬입력과 출력입력첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다.둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.출력첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.문제 해결 요약x 먼저 정렬하고y 정렬코드 설명import 및 입력받기좌표 정보 입력-import sysinput = sys.stdin.readlineimport heapqn = int(input())heap = []for _ in range(n): x, y = map(int, input().split()) hea.. 2022. 11. 11.
[Solved] BOJ: 1182 | 부분수열의 합 문제길이 N짜리 수열을 입력받아이 수열의 부분수열의 합이 S가 되도록하는 부분수열의 개수를 구해보자입력과 출력입력첫째줄에 수열의 길이 N과 부분수열의 합이 되어야하는 값 S를 입력받는다.둘째줄에 수열을 입력받는다.출력합이 S가 되도록하는 부분수열의 개수를 출력한다.문제 해결 요약i개의 수열 조합에 대한 sum을 구해 -> 브루트포스s와 같은지 확인코드 설명import 및 입력받기수열 정보를 입력받는다.-from itertools import combinationsimport sysinput = sys.stdin.readlinen, s = map(int, input().split())num = list(map(int, input().split()))부분수열의 합부분수열의 합이 S인지 체크한다.-cnt = .. 2022. 11. 7.
728x90

티스토리툴바