'알고리즘/그리디' 카테고리의 글 목록

알고리즘/그리디

백준 10162)전자레인지 python

2022. 2. 28. 12:45

백준 1931번) 회의실 배정

sehaan 2022. 2. 16. 22:23

2022. 2. 16. 22:23

접근방법) 최대한 많은 회의를 하기 위해선 두 가지를 고려해야한다.

1. 빨리 시작하는 회의를 우선 배정

2. 빨리 끝나는 회의를 다음 우선순위로 배정

이렇게 배치가 끝나면 회의 종료 시간과 다음 회의 시작시간을 비교해주어 회의수를 계산하여 주면 된다.

----------------

n = int(input())

d = [[0]*2 for _ in range(n)]

for i in range(n):

s,e = map(int ,input().split())

d[i][0] = s

d[i][1] = e

d.sort(key = lambda x: (x[1], x[0]))

cnt = 1

use = d[0][1]

for i in range(n-1):

if use <= d[i+1][0]:

cnt += 1

use = d[i+1][1]

print(cnt)

'알고리즘 > 그리디' 카테고리의 다른 글

백준 10162)전자레인지 python (0)	2022.02.28
백준 11047번) 동전 0 (0)	2022.02.14
백준 11399) ATM (0)	2022.02.11
백준 2839) 설탕배달 (0)	2022.02.08

백준 11047번) 동전 0

2022. 2. 14. 17:24

백준 11399) ATM

sehaan 2022. 2. 11. 14:42

2022. 2. 11. 14:42

접근방법)

기다린 시간의 합이 가장 작게 나올려면 소요되는 시간이 적은 순으로 정렬을 해주어야한다.

그 다음 n번째 사람 소요시간 + n-1번째 사람 소요시간의 합을 더 해준 다음 배열에 넣어주었다.

소스코드

n = int(input())

array = list(map(int,input().split()))

array.sort()

for i in range(1,n):

array[i] = array[i] + array[i-1]

print(sum(array))

'알고리즘 > 그리디' 카테고리의 다른 글

백준 10162)전자레인지 python (0)	2022.02.28
백준 1931번) 회의실 배정 (0)	2022.02.16
백준 11047번) 동전 0 (0)	2022.02.14
백준 2839) 설탕배달 (0)	2022.02.08

백준 2839) 설탕배달

sehaan 2022. 2. 8. 20:54

2022. 2. 8. 20:54

접근방식

- 최소 봉지수를 구하기 위해서는 3보단 5로 많이 나누어야한다.

따라서 킬로그램에서 3씩 마이너스를 해주어 5로 나누어 떨어지는지 확인하였다.

3을 계속 빼주어 n이 마이너스가 되어버리는 경우는 -1을 출력해주었다.

n = int(input())

cnt =0

while n >0:

if n%5 == 0:

cnt += n//5

break

n -= 3

cnt +=1

if n >=0:

print(cnt)

else:

print(-1)

풀이 중에 dp 방식으로도 풀 수 있을 거 같아서 코딩을 해보았다.

-------------

n = int(input())

d = [10001] *(n+1)

cnt = 0

d[0] = 0

d[3] = 1

for i in range(5,n+1):

d[i] = min(d[i-3],d[i-5]) + 1

if d[n] == 10001:

print(-1)

else:

print(d[n])

'알고리즘 > 그리디' 카테고리의 다른 글

백준 10162)전자레인지 python (0)	2022.02.28
백준 1931번) 회의실 배정 (0)	2022.02.16
백준 11047번) 동전 0 (0)	2022.02.14
백준 11399) ATM (0)	2022.02.11

PREV 이전 1 NEXT 다음

Tech Log 🛠️