하루일문

문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 코드 import sys input = sys.stdin.readline N = int(input()) room = [] # 회의가 금방 끝나면서 가장 빠르게 시작하는 순으로 정렬해준다 time = sorted([tuple(map(int, input().split())) for i in range(N)], key=lambda x:(x[1], x[0])) cnt = 0 end = -1 # 시작시간이 전에 끝나는 시간보다 크다면 회의를 배정해준다 for i in time: if i[0] >= end: cnt += 1 end = i[1] print(cnt) 해설 그리디 문제를 ..

문제 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라 알고리즘구현 틀 Python으로 다익스트라(dijkstra) 알고리즘 구현하기 최단 경로 알고리즘은 지하철 노선도, 네비게이션 등 다방면에 사용되는 알고리즘입니다. 이번 시간에는 Python을 이용해 하나의 시작 정점으로 부터 모든 다른 정점까지의 최단 경로를 찾는 최 justkode.kr 이 블로그를 보고 다익스트라를 만드는 법을 배워서 문제를 푸는데 활용해 보았다. 코드 # 우선순위 큐 구현 import sys, heapq ..

문제 https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 코드 from bisect import bisect_left import sys input = sys.stdin.readline n = int(input()) li = list(map(int, input().split())) # 수열을 저장하는 리스트 li_2 = [-1000000001] for i in li: # For문에서 li 순서대로 li_2에 가장 최근..

문제 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 코드 n = int(input()) n_li = sorted(list(map(int, input().split()))) m = int(input()) m_li = list(map(int, input().split())) for i in m_li: start, end = 0, n-1 while True: mid = (start + end) // 2 if n_li[mid] == i: print(1) break i..

문제 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 코드 import sys input = sys.stdin.readline n = int(input()) tax = list(map(int, input().split())) limit = int(input()) start, end = 0, max(tax) while start = total_tax: start = mid + 1 # 예산보다 작을경우 end를 줄여서 mid값을 줄여준다. else: end = mid -1 print(end)

문제 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 코드 for t in range(int(input())): # 오늘 본 숫자를 입력받고 이진탐색으로 풀기 위해 오름차순 정렬해준다 see_n = int(input()) see = sorted(list(map(int, input().split()))) write_n = int(input()) write = list(map(int, input().split())) # 적은 숫자만큼 반복한다 for n in write: # 시작과 끝을 정해준다 start, end =..

문제 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 코드 def fibonacci(n) : if n >= 3 : for i in range(2, n) : # 더해주면서 더한 수의 리스트를 차례대로 붙여넣는다 fibonacci_0.append(fibonacci_0[i-1]+fibonacci_0[i]) fibonacci_1.append(fibonacci_1[i-1]+fibonacci_1[i]) # 제일 마지막 수 출력 print(fibonacci_0[n],fibonacci_1[n]) T = int(input()) for t in range(T) : # 값을 받을때 마다 초기화 fibonacci_0 = [1,..

문제 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 코드 n = int(input()) grape = [0] + [int(input()) for _ in range(n)] drink = [0] * (n+1) drink[1] = grape[1] # n==1이면 drink[2]가 없으니 인덱스 에러가 남 if n != 1: drink[2] = sum(grape[1:3]) for i in range(3, n+1): # 연속을 마시지 않을 때 - drink[i-1] # drink[i-2]을 마실 때 # drink[i..