그리디 알고리즘 -(1)

이것이 코딩테스트다 (연습문제 1/2 풀기 + 백준 문제 풀기)

 

이것이 코딩테스트다

1. 모험가 길드

2. 곱하기 혹은 더하기

3. 문자열 뒤집기

#모험가 길드 => 공포도가 x인 모험가는 반드시 명 이상으로 구성한 모험가 그룹에 참여해야함. 최대 몇개의 모험가 그룹? //28
'''
n = int(input())
num = list(map(int, input().split()))
print(num)

num.sort(reverse = True)
list2= []

for i in range(0,n):
    cnt=0
    while i<n and num[i] <= (n-i):
        i+=num[i]
        cnt+=1
    list2.append(cnt)

print(max(list2))
'''
#곱하기 혹은 더하기  => 사이에 연산자 +혹은 x를 넣어서 만들 수 있는 가장 큰 수를 출력 //11

'''
s = input()
s2=[]
result=[]

for i in range(0,len(s)):
    s2.append( int(s[i]))

for i in range(0,len(s2)-1):
    if s2[i]+s2[i+1] < s2[i]*s2[i+1]:
        result.append(s2[i]*s2[i+1])
        s2[i+1] = result[i]
    else:
        result.append(s2[i]+s2[i+1])
        s2[i+1] = result[i]

print(result[-1])
'''
#문자열 뒤집기 =>연속된 하나 이상의 숫자를 잡고 모드 뒤집기-> 한번의 행동일때, 최소 행동 횟수구하기 => 숫자가 바뀌면 그 숫자 list행 //10

'''
s = input()
s2=[]
rem=[]
cnt =[0]*2

for i in range(0,len(s)):
    s2.append(int(s[i]))

for i in range(0,len(s2)-1):
    if s2[i]!=s2[i+1]:
        rem.append(s2[i])

for i in range(0,len(rem)):
    if rem[i]==1:
        cnt[1]+=1
    else:
        cnt[0]+=1

print(min(cnt))
'''

 

문법 정리)

1. 문자열을 split()했을 때, abc가 a,b,c로 나눠질줄 알았는데 아니고 대신 문자열 그 자체를 배열로 취급해 인덱스 번호기준으로 slice가능하기 때문에 그것을 이용할 수 있음.

2. 문자열 s가 1234일때 s[0]이 1이고 ,,,s[3]=4이기때문에 순간 신나서(?) 문자열을 쪼갰다는 것을 잊고 숫자처럼 곱함 => 안 됨. 문자열은 서로 곱하기 연산이 불가능함 => 문자열을 int형으로 바꿔주기 위해서 for문을 새로 만들어서 돌려서 새로운 list에 저장해서 사용

 

---

백준 2839

 

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

#n킬로그램을 배달해야할때, 3키로와 5키로 봉지를 가지고 최소개수를 옮기고 싶음.
#5키로그램을 우선으로 선택하고 나머지를 3키로짜리로 가져가야함.

n = int(input())
cnt=[]
y=0

for i in range (0,n//5+1):#i에 5의개수-1이 들어있음
    x = n- (5*(i))
    #print(x)
    if x%3!=0:
        cnt.append(-1)
    else:
        cnt.append(x//3 + i)

cnt = set(cnt)
cnt = list(cnt)
cnt.sort()
#print(cnt)

for i in range(0,len(cnt)):
    if cnt[i]==-1 and i==len(cnt)-1:
        print(cnt[i])
        break
    if cnt[i]!=-1:
        print(cnt[i])
        break

간단한 문제에 가깝지만 -1을 제외한 숫자중 가장 작은 숫자를 선택해야하는데 -1을 어떻게 처리할지 고민할 필요가 있던 문제같음.

 

문법정리)

나눗셈 -> '/'을 통해서 가능하고 실수로 표현

몫 -> '//'을 통해서 가능

나머지 -? '%'를 통해서 가능