백준 C++ 2839번 설탕 배달 ( 그리디 )

이번 주는 조금 바쁩니다.

4월에 일정이 꽤 많네요.

 

저번주말에 사람들이 다들 꽃구경을 갔더라고요.

저는 알바를 했습니다....

아쉬운 일이지만.. 네 그렇습니다.

 

오늘은 엄마아빠 생신이라서

후딱 문제 풀고

저녁에 이벤트를 후딱 준비해야 합니다.

 

사실 별건 없고

전날 생각한 이벤트인데

카드를 뽑아서 좋은 카드를 3장 모으면 현금을 주는

그런 걸 생각했습니다.

기대되네요 ㅎ

 

오늘은 설탕을 배달하러 가봅시다.

시작하기 전에 초콜릿을 먹고 하겠습니다.

몰티져스를 샀거든요 ㅎ!!

 

---

 

 

설탕을 배달하는데

최소한으로 받고 싶다...

 

아 예전에 그 최소한으로 하는 거 있었는데 기억이 잘 안 나네요.

 

정답률이 38 퍼입니다..

 

원래 5로 나누고

0이랑 3이 나올 때 그리고 안 나올 때로 생각했는데

문제는 나머지가 4가 나올 때가 문제다.

 

9의 경우겠다.

5 하고 4 하면 사실 이건 안된다며 -1을 낼 텐데

3으로 하면 3으로 딱 떨어진다.

 

이 4 부분만 생각하면 될 거 같다.

 

써보고 생각하니 제약이 많았다..

6은 3으로 나누면 2로 딱 떨어지는데

5로 나누면 1이 남고

12는 3으로 나누면 4로 되는데..

5로 나누면 2가 남는다...

..

이러면 숫자를 4로 생각하면 안 된다.

 

일단 나머지가 3이 나오는 경우와 0이 나오는 경우만 해주고

나머지는 또 다른 예외식이 필요하다.

 

1,2,4의 경우

일단 3으로 나눠보는 게 맞을 거 같다.

일단 5로는 절대 안 나오기 때문..

 

21, 12, 9가 그런 경우겠지..

 

하며 작성했다.

 

어...

근데 예제 마지막이 문제였다.

11인데...

11은 5 한개 3 두 개로 된다.

근데 이식으로는 -1이 나온다.

 

.. 긁적..

근데 만약에 51이라고 치자.

5를 45개까지 하고 9개

3을 2개 하면.. 총 11개이다.

이러면 흠.. 6을 남겨놔야 하는 상황인가?

 

다시 생각하니 54도 문제다.

3으로 나눠 떨어지는데.. 위 식으로 하면..

그냥 tmp /3이어서 최소로 나오지 않는다.

 

 

그럼 

예외가 참 많을 거 같은데..

 

에잇.. 모르겠다.

 

패턴을 못 찾은 느낌이다.

 

인지 씨에게 주절주절 쓰던 중..

 

뭔가 알아낸 느낌이다.

5로 나눴을 때

 

0이면 그냥 5 개수만 쓰기

 

1일 경우 5를 한 개 빼고 3을 2개 쓰면 되고

 2일 경우 5를 두 개 빼고 3을 4개 쓰면 된다.
3일 경우 5를 빼지 않고 3을 1개 쓰면 되고

 4의 경우 5를 한 개 빼고 3을 3개 쓰면 된다.

 

미쳤다!!

 

해보자!

 

 

4와 7은 3으로도 5로도 못 만들지만

그 이상은 다 만들 수 있다.

두 시간에 걸쳐 짠 코드..

과연 답이 맞을까..?

 

맞았다..!!

두 시간 만에.. 푼 문제..

하지만 이 문제는 뭔가 최적의 효율일 거 같지 않았다.

 

인지 씨를 찾은 나.

 

이 문제는 그리디 문제라고 했다.

그리디? 누구 쇼

 

그리디

당장 눈앞에 보이는 최선의 선택만 고르는 방식

탐욕.. 알고리즘이라고 한다.

 

800원을 줄 때

우리는 본능적으로 500원부터 꺼낸다.

그리고 100원짜리를 차액으로 준다.

가장 큰 거부터 빠르게 하는 거지!

 

하지만 우리는 지금 

얼마를 줘야 할지 모르니까

일단 작은 걸로 주다가

큰 걸 줄 수 있을 때 주는 것.

 

지금은 5로 줘야 하는데 5로 못주는 예외들을

if문으로 처리했는데

 

이런 그리디 문제는

5kg으로 줄 수 있는지 보고

안되면 3kg짜리로 하나씩 주면서 깎아서

5kg로 줄 수 있는지 보는 것!!

 

그래서 while문으로 계속 나눠주면서

안 나눠지면 cnt 해주고 3씩 빼주는 것이다.

 

그다음에 5로 나눠지면? 출력하게 되는 것 3의 횟수와 함께!

 

이 while문을 탈출했다면?

그 녀석은 애초에 5로 나눠지지 않는 친구로 -1을 출력해 주면 된다.

 

 

이렇게 풀어주면

if else가 많아서 헷갈리진 않는다.

 

---

 

두 시간 동안 패턴을 찾았다..

 

근데 이 패턴도 그리디라고 할 수 있을 거 같긴 하다.

뭐랄까.. 결국 나도 5로 나눠지는 걸 찾았고

5로 나눠지면 나머지가 1 2 3 4인데 

3은 그냥 하나 더 해주면 되고 1,2,4 만 패턴을 찾아주면 됐다.

 

사실 뭐 3의 배수 뒷자리를 보려고 했는데

3 6 9 2 5 8 1 4 7 0

으로 뭐 ㅋㅋㅋㅋㅋㅋ

모든 숫자가 다 들어가서 탈락

 

그래도 풀었다.

오래 걸렸다.

머리가 아프다.

 

이제 얼른 케이크 사가지고 와야지 ㅎㅅㅎ