백준 1475번 문제

백준 1475번 문제 :한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다)

 

안녕하세요. 이번에는 백준 1475번 문제를 들고 왔습니다. 일단 문제의 핵심을 생각해봅시다.

 

이문제의 핵심은 각 자릿수를 체크를 해야 하고, 자릿수마다 숫자도 체크를 해 세트의 개수를 구하는 거죠.

그럼 어떻게 알고리즘을 짜야할까요?

 

일단 변수 설정부터 들어가 봅시다.

저 같은 경우에는

주어진 수 : num

각 자릿수 : data

세트의 개수 : count

상태 : reSet

세트 안의 숫자수 : check[10] (0,1,2,3,4,5,6,7,8,9)

각 자릿수의 숫자 : digit

이렇게 각 변수마다 의미를 부여해 만들었습니다.

그럼 일단 자릿수부터 구하는 코드를 구현해봅시다..

 

여기서 보시면  data의 초기값은 10으로 되어있죠.

num을 data로 나누었을 때 몫이 10 이상이 되면 data자릿수가 아니기 때문에 data의 10을 곱해주면서 검사를 했습니다.

그리고  주어진 수가 십의 자리보다 작은 경우는 일의 자리밖에 없으므로 data에 1을 대입합니다

마지막으로 num을 data로 나누었을 때 9 이하가 되면 break를 걸어 while문에서 나가도록 만들었습니다.

긴 사진이지만 이해하면 간단한 코드입니다. 일단 num을 data로 나눈 몫을 digit에 저장합니다.

그리고 digit를 check인덱스로 사용해 해당되는 값이 0 이상이면 1을 빼주고 0이면 reSet을 1로 바꿔 check의 인덱스 값들을 전부 1을 더해집니다.

 

숫자 6과 9는 연동 할 수 있으니 digit가 6이나 9일때도 한 번 체크해주시면 될 것 같습니다.

이렇게 1475번 문제도 해결할 수 있습니다.

다음에도 수학관련 알고리즘 문제의 풀이과정을 들고오겠습니다.

긴 글 봐주셔서 감사합니다