무니화니

이번 문제는 공유기 설치라는 문제이다. 이 문제 또한 집의 개수가 매우 많을 수 있고, 좌표의 범위도 매우 넓다. 그렇기에 이중 for 문을 써서 풀 수도 있지만, 2초라는 시간 제한에 걸려서 시간 초과가 뜰 것이다. 알고리즘 해설 이분 탐색을 통해 풀었다. 코드 n,c=map(int,input().split()) data=[int(input()) for _ in range(n)] data.sort() l,r=0,data[-1]-data[0] res=0 while l=mid: answer+=1 curr=i if answer

오늘의 문제! https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 위 그림처럼 나무를 일정한 높이로 자르고, 윗 부분을 가지고 사용한다. 코드 n,m=map(int,input().split()) data=list(map(int,input().split())) data.sort() low=0 high=data[-1] answer=0 while low

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 한 회의실을 사용하기 위해서 제일 많이 회의를 할 수 있는 방법을 찾는다. import sys input=sys.stdin.readline n=int(input()) data=[list(map(int,input().split())) for _ in range(n)] data.sort(key=lambda x:[x[1],x[0]]) start,end=data[0] cnt=1 for i in range(1,n): start1,end1=data[i] if end

평범한 dynamic programming 문제이다. n,k=map(int,input().split()) coindata=[] for _ in range(n): coindata.append(int(input())) coindata.sort() values=[0 for _ in range(k+1)] values[0]=1 for i in coindata: for j in range(1,k+1): if j-i>=0: values[j]+=values[j-i] print(values[k]) 0원부터 k원까지 개수를 셀 수 있는 리스트를 만들고, 거기에 1월부터 k원까지 가능한 개수를 모두 센다. 반복문에서, 현재 돈의 크기에 (현재 돈 - 동전의 크기)일 때의 개수를 더해준다.

골드 3 난이도의 텀 프로젝트라는 문제를 풀어보았다. 문제를 해석해보자면, 서로서로 프로젝트를 같이 하고 싶은 학생들끼리 그룹을 짜주려고 하는데, 4번이 7번, 7번이 6번 6번이 4번, 즉 서로서로를 꼬리잡기 하듯이 고르면 같은 그룹에 넣어주는 구조이다. 만약 자기 자신을 고르면, 혼자 팀이 된다. (현실 반영...) 내용 자체는 쉽지만 구현하기가 어려웠다. 코드이다. t=int(input()) for _ in range(t): n=int(input()) data=[0]+list(map(int,input().split())) visited=[False for _ in range(n+1)] res=0 for i in range(1,n+1): if visited[i]: continue num=i q=[nu..

이번에는 소수의 연속합이라는 골드 3 난이도의 문제를 풀어 보았다. 소수판별을 이용하면 쉽게 풀 수 있는 문제이다. 그러나, 두 개의 포인터, 한 마디로 기준을 두 개를 잡고 풀어야 하는 문제여서 독특했다. n=5*10**6 a=[False,False]+[True]*(n-1) for i in range(2,n+1): if a[i]: for j in range(2*i,n+1,i): a[j]=False primes=[] for i in range(n): if a[i]: primes.append(i) n=int(input() ) l,r=0,0 answer=0 while n>=primes[r]: sumNum=sum(primes[l:r+1]) if sumNum>n: l+=1 elif sumNum

해당 문제는 더하기 연산을 하면 되는 단순한 문제처럼 보인다. 하지만, 이 문제의 포인트는 처음에 몇개의 연산을 해야하는지, 제한을 주지 않았다. 그렇기에, input의 끝, EOF 까지 input을 받아야한다. import sys lines=sys.stdin.readlines() for line in lines: A,B=map(int,line.split()) print(A+B) #================ while True: try: a,b=map(int,input().split()) print(a,b) except EOFError: break 두 가지 방법으로 해당 문제를 해결 할 수 있다. lines에서 모든 줄의 input을 받는 거다. 이 때 사용하는 함수가 sys.stdin 모듈의 rea..

오늘의 문제는 계산을 요하는 간단한 문제이다. 어렵진 않으나 만약 나중에 또 풀려고 하면 기억이 안 날 것 같아 정리하려고 한다. a,b=map(int,input().split()) print(a//b, end='') if a%b: i=0 print('.', end='') while a%b and i

문제가 단순히 소수를 판단하는 문제인 줄 알았는데, 극악의 정답률을 자랑하는 데에는 이유가 있다. t=int(input()) data=[] for _ in range(t): data.append(list(map(int,input().split()))) num=0 primes=[] for i in data: num=max(sum(i),num) a=[False,False]+[True]*(num-1) for i in range(2,int(num**0.5)+1): if a[i]: primes.append(i) for j in range(2*i,num+1,i): a[j]=False for i in range(len(a)): if a[i]: primes.append(i) for i in data: limit=sum..

오늘의 문제는 BOJ 2206, 벽 부수고 이동하기이다. 문제 내용은 단순히 bfs를 이용하면 될 것 같지만, 이동하면서 벽을 한 번 깰 수 있다는 조건이 있어서 기존의 방식으로 접근할 수 없었다. from collections import deque m,n= map(int,input().split()) data=[[1e10]*n] for i in range(m): data.append([1e10]+list(map(int,list(input())))) visited=[[[0,0] for _ in range(n+1)] for _ in range(m+1)] q=deque() q.append([1,1,0]) visited[1][1]=[1,1] dx=[[0,1],[0,-1],[1,0],[-1,0]] def bf..