n,k = map(int,input().split())
a = []
coin = 0
for _ in range(n):
a.append(int(input()))
a.sort(reverse=True)
for i in a:
if k >= i:
if k%i ==0:
coin += k//i
break
coin += k//i
k = k%i
print(coin)
[ 해결 아이디어 ]
* 그리디(탐욕) 알고리즘
: 눈 앞의 이익만 우선 추구하는 알고리즘
( greedy : 탐욕스러운, 욕심이 많은 )
--> knapsack문제, 동전 문제(각 동전은 작은 동전의 배수)
입력에 보면 Ai는 Ai-1의 배수 라는 조건이 있다.
즉, 동전이 1, 5, 10, 50, 100 .. 이런 식으로 큰 동전은 작은 동전의 배수가 된다.
이러한 유형은 GREEDY 알고리즘으로 해결 할 수 있다.
[ 해결 코드 ]
n,k = map(int,input().split())
a = []
coin = 0
for _ in range(n):
a.append(int(input()))
a.sort(reverse=True)
# GREEDY
for i in a:
coin += k//i
k = k%i
print(coin)
n = int(input())
bag = 0
while 1: # 계속 반복함
if n%5 == 0: #5의 배수이면
bag += n//5 #몫 만큼 bag에 더함
break #n이 5의 배수이면 몫 만큼의 가방만 필요하므로 끝!
# (예) n=10이라면 n//5 = 2 -> 2개의 가방만 있으면 됨
# 예외처리
if n<3:
bag = -1
break
# 3kg은 빼주면서 가방 하나씩 더함
n -= 3
bag += 1
print(bag)
# box1의 a점(ax,ay), box1의 b점(bx,by)
ax,ay=0,0
bx,by=0,0
# box2의 c점, d점
cx,cy=0,0
dx,dy=0,0
def point(ax,ay,bx,by,cx,cy,dx,dy):
if((ax,ay)==(dx,dy) or (bx,by)==(cx,cy) or (bx,ay)==(cx,dy) or (ax,by)==(dx,cy)) :
return True
else:
return False
def line(ax,ay,bx,by,cx,cy,dx,dy):
# 꼭짓점 하나 일치
if(((bx,by)==(cx,dy) and by>cy) or (((bx,ay)==(cx,cy) and dy>ay))
or((dx,cy)==(ax,ay) and by>cy) or ((dx,dy)==(ax,by) and dy>ay)
# 변 일치
or ((bx,by)==(cx,dy) and (bx,ay)==(cx,cy)) or ((ax,ay)==(dx,cy) and (dx,dy)==(ax,by))
or ((cx, cy) == (ax, by) and (bx, by) == (dx, cy)) or ((ax, ay) == (cx, dy) and (dx, dy) == (bx, ay))
# 그 사이(a,b의 한 변에 c,d가 겹침)
or (ax==dx and (ay<cy<by or ay<dy<by)) or (bx==cx and (ay<cy<by or ay<dy<by))
or (by==cy and (ax<cx<bx or ax<dx<bx)) or (ay==dy and (ax<cx<bx or ax<dx<bx))
# 그 사이(c,d의 한 변에 a,b가 겹침)
or (ax == dx and (cy < ay < dy or cy < by < dy)) or (bx == cx and (cy < ay < dy or cy < by < dy))
or (by == cy and (cx < ax < dx or cx < bx < dx)) or (ay == dy and (cx < ax < dx or cx < bx < dx))
# 내부 한 변 일치(ab안에 cd)
# or (ay==cy and ax<cx<bx and ax<dx<bx and ay<dy<by) or (ax==cx and ay<cy<by and ay<dy<by and ax<dx<bx)
# or (by==dy and ax<cx<bx and ax<dx<bx and ay<cy<by) or (bx==dx and ay<cy<by and ay<dy<by and ax<cx<bx)
# 내부 한 변 일치(cd안에 ab)
# or (ay==cy and cx<ax<dx and cx<bx<dx and cy<by<dy) or (ax==cx and cy<ay<dy and cy<by<dy and cx<bx<dx)
# or (by==dy and cx<ax<dx and cx<bx<dx and cy<ay<dy) or (bx==dx and cy<ay<dy and cy<by<dy and cx<ax<dx)
):
return True
else:
return False
def null(ax,ay,bx,by,cx,cy,dx,dy): #cy>by or ay>dy
#dx<ax or bx<cx or min(cy,dy)>max(ay,by) or min(ay,by)>max(cy,dy)
#우,좌,상,하 바깥에서 안 접할 때
if(bx<cx or dx<ax or by<cy or dy<ay):
return True
#안에서 안 접할 때
elif(bx-ax<dx-cx and by-ay<dy-cy and (cx<ax<dx and cx<bx<dx) and (cy<ay<dy and cy<by<dy)): #속에 들어감
return True
elif(bx-ax>dx-cx and by-ay>dy-cy and (ax<cx<bx and ax<dx<bx) and (ay<cy<by and ay<dy<by)): #속에 들어감
return True
else:
return False
# main 함수
ax,ay,bx,by=map(int,input().split())
cx,cy,dx,dy=map(int,input().split())
if(line(ax,ay,bx,by,cx,cy,dx,dy)):
print('LINE')
elif (point(ax,ay,bx,by,cx,cy,dx,dy)):
print('POINT')
elif(null(ax,ay,bx,by,cx,cy,dx,dy)):
print('NULL')
else:
print('FACE')
[ 코드 ] **하노이탑 파이썬 - 시간초과가 떴다면** print(count) 대신print(2**n - 1) 를 해라! -> 하노이탑의 총 옮긴 횟수는 2^n - 1으로 정해져 있다. (하지만 개인적으로 옮길 때 마다 count를 증가시켜서 총 count를 출력하는 게 맞다고 생각한다. 근데 그렇게 하면 시간 초과가 된다..)
import sys input=sys.stdin.readline n = int(input()) #count = 0 #옮긴 횟수 #ans='' def hanoi(disk_num,from_peg,to_peg,tmp_peg): global count,ans if(disk_num==1): print(from_peg,to_peg) # ans += '{} {}\n'.format(from_peg,to_peg) # count += 1 return hanoi(disk_num-1,from_peg,tmp_peg,to_peg) print(from_peg,to_peg) # ans += '{} {}\n'.format(from_peg, to_peg) # count += 1 hanoi(disk_num-1,tmp_peg,to_peg,from_peg) print(2**n - 1) #count를 하니 시간 초과 뜸 # (처음)1 에서 (최종)3으로 이동함 # 2는 거치는 곳일 뿐! hanoi(n,'1','3','2') #print(count) #print(ans)
[ 결과 ] 와.. 진짜 시간초과 너무한거 아니냐고.... 몇 번을 시도해서 결국 통과되었다.. 너무해..
#n: student num
#k : max people# in one room
n, k = map(int, input().split())
st = [[0]*2 for _ in range(6)] #성별2개 6학년
#입력
for _ in range(n):
# st[학년][성별]
s,y= map(int, input().split())
st[y-1][s-1] += 1
# print(st[y-1][s-1])
room_num=0
for a in range(6):#학년
for b in range(2):#성별
#print(st[a][b])
#math.ceil써도 :)
if(st[a][b]%k == 0):
room_num += st[a][b]/k
else:
room_num += st[a][b]//k + 1
print(int(room_num))
#시간초과 시 추가하면 좋은 구문
# https://www.acmicpc.net/board/view/44990
import sys
input=sys.stdin.readline
n = int(input()) #명령의 수
stack=[]
def push(x):
#리스트의 마지막에 추가
stack.append(x) #딱히 int(x)할 필요는 없을 듯
def pop():
if(len(stack)==0):
print(-1)
else:
print(stack.pop())
def size():
print(len(stack))
def empty():
if(len(stack)==0): #비면
print(1)
else: #안 비면
print(0)
def top():
if(len(stack)==0):
print(-1)
else:
print(stack[-1])
for i in range(n):
command=input().split() #push 1 같은 애들 분리
if(command[0] == 'push'):
push(command[1])
if (command[0] == 'pop'):
pop()
if (command[0] == 'size'):
size()
if (command[0] == 'empty'):
empty()
if (command[0] == 'top'):
top()
