[백준] 파이썬/ 그리디 11047_동전0 , 1541_잃어버린 괄호

📌11047 동전0

 

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

11047번: 동전 0

 

 

내 풀이

import sys
input= sys.stdin.readline

coins=[]
coinCnt=0

n,k = map(int,input().split())

for i in range(n):
    coins.append(int(input()))

left=0
for j in range(len(coins),0,-1):
    coinCnt+=k//coins[j-1]
    k=k%coins[j-1]

print(coinCnt)

 

동전배열을 거꾸로 돌며 나머지 값을 계속 나눠주고 , 몫값을 동전의 개수로 cnt한다

한번에 정답이었지만, 모든 동전에서 계산을 해야하기 때문에 불필요한 작업을 줄일 수 없을까? 생각했다.

 

검색해보니 for문 안에서 if k==0 조건을 줘서 반복문을 돌기 전에 끝내는 경우가 있어서 넣어봤더니 큰 시간 차이가 없었다,

 아마 동전의 종류가 엄청나게 많아지면 효과가 있을 것 같다.

 

---

 

📌1541_ 잃어버린 괄호

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

1541번: 잃어버린 괄호

내 풀이

input= sys.stdin.readline

problem = input().strip()

symbol = re.compile('\D').findall(problem)
print((problem[:problem.index('-')]))  // 55

 

처음 생각한 몇가지 방법 

1. 정규표현식으로 연산을뽑아서 나머지 숫자로 계산하자

2. for 문을 돌며  '-', '+'일때를 다 계산하자

 

일단 두가지 방법 다 접근이 틀렸다.

그 이유는 문제가 그냥 계산하는 것이 아닌 최소값을 구하는 것이기 때문 .. 

 

오늘 하루종일 코딩하다가 와서 피곤한 상태로 풀었더니 문제를 제대로 읽지 않는 습관이 도졌다. ㅠㅠㅠ

 

 

다른 풀이

ans=0
problem = input().split('-');
for i in problem[0].split('+'):
    ans+=int(i)

for j in problem[1:]:
    for k in j.split('+'):
        ans-=int(k)

print(ans)

1) '-'가 나오기 전까지 더한다

2) '-'가 나온 뒤의 값들은 모두 뺀다

 

최소값이 나와야 하기 때문에 - 나온 이후로부터는 괄호를 다 묶어서  빼버리는 것이 가장 최소인 방법이었다.

 

 

💙 문제를 보고나서 충분히 고민하고 푸는 습관을 가져야 겠다.

단순히 빠르게 풀고 싶어서 휙 읽고 풀었더니 완전 오랫동안 혼자 다른문제를 풀었다...