밀리지 말고 잘 쓰자..^^
CH1.그리디 문제(백준)
🗨 11047번 : 동전 0
https://www.acmicpc.net/problem/11047
👆 입력 받은 동전 단위를 내림차순으로 정리한 다음, 큰 단위부터 만들어야 하는 값을 나누면서 계산함.
n,k = map(int,input().split())
data=[]
count =0
while n!=0:
data.append(int(input()))
n-=1
#print(data)
data.sort(reverse=True)
#print(data)
for x in data:
if(k>0):
if(x>k): continue
else:
count+=(k//x)
k%=x
else:
break
print(count)🗨 2875번 : 대회 or 인턴
https://www.acmicpc.net/problem/2875
👆 for문을 통해서 [n-0,m-k],[n-1,m-(k-1)],...[n-k,m-0] 각 경우의 수에 대해서 계산함.
풀이 코드
n,m,k = map(int,input().split())
result = 0
for x in range(0,k+1):
result = max(result,min((n-x)//2,m-(k-x)))
print(result)🗨 10610번 : 30
https://www.acmicpc.net/problem/10610
👆 30의 배수가 되려면 일단 마지막 자리 수는 0이 되어야 함. 따라서 입력 받은 수에 0이 포함되어 있는지 확인하고, 없다면 바로 -1 출력. 있다면, 입력 받은 각 자리수의 합이 3의 배수가 되는지 확인하면 됨. 3의 배수까지도 성립한다면,입력받은 수를 내림차순으로 나열하면 30의 배수가 되는 가장 큰 수를 구할 수 있음.
data = list(input())
sum=0
isZero = False
for x in data:
num = int(x)
sum+=num
if num==0:
isZero=True
if isZero==False:
print(-1)
else:
if(sum%3==0):
data.sort(reverse=True)
str ="".join(data)
print(str)
else:
print(-1)참고
- input을 list 형태로 받기
data = list(input()) - list의 원소들을 공백 없이 string으로 변환하기
str="".join(data)
🗨 1783번 : 병든 나이트
https://www.acmicpc.net/problem/1783
👆 그려보다가 포기함. ㅎ 걍 코드 참고함
-
N이 3보다 작거나 M이 7보다 작은 경우 이동 횟수가 4번이 되지 않는 경우로 간주한다.
-
체스판의 N이 3보다 크고 M이 7보다 큰 경우 4번 이상 이동할 수 있다. 나이트는 위, 아래로 움직일 수 있기 때문에 N이 3보다 크다면 제한 없이 움직일 수 있어 이동 경로에 영향을 주지 않는다. M은 오른쪽으로만 이동할 수 있기 때문에 이동 경로에 영향을 주게 된다.
-
4번 이상 이동하는 경우, 4번의 경우를 한 번씩은 사용해야 하기 때문에 오른쪽으로 두 칸 움직이는 2,3번 이동을 한 번씩 하고 나머지는 오른쪽으로 한 칸씩 움직이는 1,4번 이동을 반복한다.
참고: https://it-college-diary.tistory.com/entry/그리디-알고리즘-백준-1783번-병든-나이트?category=925374 [CodeLog]
N,M = map(int,input().split())
if N==1:
count = 1
elif N==2:
count = min(4,((M-1)//2)+1)
elif M<7:
count = min(4,M)
else:
count = M-2
print(count)🗨 11000번 : 강의실 배정
https://www.acmicpc.net/problem/11000
👆 첨에 걍 무지성으로..배열에 시간 입력 받은 거 삽입하고 비교하는 코드로 짜봤는데 시간초과 ㅎ 이것도 깔꼼하게 코드참고^^..
import heapq
import sys
#heapq : 리스트를 최소 힙처럼 다룰 수 있도록 도와주는 모듈
N=int(input())
C=[]
h=[] #heapq에 이용할 리스트
#split() : 공백을 기준으로 input을 쪼개어 리스트 형태로 반환
#map() : split된 여러개의 input에 대하여 일괄적으로 형 변환
#sys.stdin.readline(): input과 사용방법 동일, 개행문자(\n)까지 함께 입력받는다
for i in range(N):
C.append(list(map(int,sys.stdin.readline().split())))
C = sorted(C,key = lambda x:x[0])
# C를 정렬하는데, 첫번째 인자 기준으로 정렬
# [[1,3],[2,4],[3,5]]
for i in range(N):
if len(h)!=0 and h[0]<=C[i][0]:
#비어있지 않고,
# 현재 heap에 있는 값이 지금 리스트의 start time보다 작으면
# pop을 해준다 -> 같은 강의실에 배정된다는 뜻
heapq.heappop(h)
#그게 아닐 경우는 강의실을 하나 더 배정하는 경우이므로
#C[i][1] end time을 heap에 넣어준다.
heapq.heappush(h,C[i][1])
#heapq에는 end time을 넣음.
print(len(h))참고
-
C 리스트 안에, [start_time,end_time] 형태로 삽입하기
for i in range(N): C.append(list(map(int,sys.stdin.readline().split()))) -
정렬시, 첫번째 인자 기준으로 정렬하기
C=sorted(C,key = lambda x:x[0])
🗨 1931번 : 회의실 배정
https://www.acmicpc.net/problem/1931
👆 앞에 강의실 배정 푼 다음이라 그 코드를 좀 활용함. 첨에 짰을 때, 100%에서 틀렸다고 나와서 반례 여러개 해봤는데,sort시에 end time 같을 때 start time을 오름차순으로 정렬해줘야 했다. 그 부분 고치니까 통과쓰
import sys
N = int(input())
C =[]
stack = []
for i in range(N):
C.append(list(map(int,sys.stdin.readline().split())))
C = sorted(C,key = lambda x: (x[1],x[0]))
#C 에서 key값이 같은 경우, 오름차순 정렬 하고 싶음
# for i in range(N-1):
# for j in range(i+1,N):
# if C[i][1]==C[j][1]:
# #key값이 같을 경우
# if C[i][0]>=C[j][0]:
# #앞에 start time이 더 크면 swap
# C[i][0],C[j][0]=C[j][0],C[i][0]
# else:
# break
#print(C)
for i in range(N):
if len(stack)==0:
stack.append(C[i][1])
elif len(stack)!=0 and stack[-1]<=C[i][0]:
stack.append(C[i][1])
print(len(stack))
참고
- sorted : 정렬한 뒤에 또 다른 조건으로 정렬하고 싶은 경우
C = sorted(C,key = lambda x: (x[1],x[0]))
C를 x[1] 즉, end time으로 먼저 정렬한 뒤, 정렬한 결과에 대해 start time인 x[0] 기준으로 정렬한다. 이렇게 하면 end time이 같은 경우에 대한 처리를 정상적으로 할 수 있음.
