1475번: 방 번호

1475번 방 번호

1475번 방 번호 클릭시 문제로 이동

1) 문제

---

2) 문제 설명

숫자 0~9가 1세트이고 주어진 숫자를 표현하려면 몇 세트를 사용해야하는가?

(단, 6과 9는 서로 뒤집어서 사용할 수있다.)

Ex) 1269 = 1세트

1266 = 1세트

9999 = 2세트

---

3) 풀이 과정

사용된 숫자들의 갯수를 세고 가장 많이 사용된 수를 찾으면 된다.

---

4) 핵심

서로 돌려 사용할 수 있는 6,9의 갯수는

(6,9를 홀수개를 사용하면 n세트하고 1개를 사용했기에 n+1세트를 구매해야하므로 천장함수를 사용한다.)

※는 천장함수(올림함수)로 실수 x보다 크거나 같은 정수 중에서 가장 작은 정수

(쉽게 생각하면 소숫점이 있으면 올림한다고 생각하면된다)

Ex)                         

---

5) 핵심 코드

check[6] = (check[6] + check[9] + 1) * 0.5;
 
for (int i = 1; i < 9; i++) 
{
    if (check[r] < check[i]) 
        answer = check[i];
}

천장 함수(ceil)대신해서 간단한 수식인 (A+B+1)/2 로 대체하였다.

※check의 타입은 int형이기 때문에 소숫점 아래는 버려진다.

---

6) 기타

요즘들어 공부 의욕이 줄고 있어서 큰일이다.

이번 문제도 엄청 예전에 풀어놓고 포스팅을 미루다 미루다 지금하게 되었다.

공부 의욕을 다시 잡아야 할텐데...

조금만 더 간단한 수학들을 이용한 알고리즘을 풀고

DP(동적계획법) 같은 것으로 넘어 가려고 한다.

아직은 DP에 대하여 설명할 자신이없어서 미루고 있었지만 언제까지나 미룰수는 없는 법

(이해하는건 괜찮은데 남에게 설명하는건 너무 어려운 것 같다)

최대한 쉽게 설명한다고 풀어쓰고 있어서 더 난잡해 보일 수도 있습니다. ㅠ

읽기 불편한 부분이나 이해가 되지 않는 부분은 댓글 주시면 수정하겠습니다.

다른 알고리즘이나 다른 의견이 있으시면 댓글 주시면 감사하겠습니다 :)