[C]백준 Q.4375 1

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

 

이번은 코팅테스트 - 기초 라고 적힌 백준에서 제공중인 온라인강의의 문제집문제를 시작했다

그런데 뭔가 뎁스가 깊어...

코드 플러스 -> 코팅테스트 기초 -> 수학의 문제들을 우선 풀거다

기초라고 적힌거 만큼 처음 문제는 그냥 연산자 쓴거 출력하는 문제라 블로그에 올릴쓸글이 없어서 깃에 올리기만하고 글은 패스

두번째 문제는

제목이 1 이라는 이상한 문제다

분명 기초문제라고 했는데.... 정답률이 32퍼

뭐 아무튼 문제를 받고 바로 아이디어를 써내려가서 대충 코드를 처음 썻었다.

그게 첫번째로 한게

111111~ 막 이렇게 적힐 애들을 문자열로 뒤에 한글자씩 더해서 atoi로 숫자로 바꾸고 나머지연산을 해서 0이면 문자수를 리턴

상식적으로 문제내준걸 그대로 바꿔적은거라 이게 왜 정답률이 30퍼센트대일까 궁굼해하며 예제 답을 돌렸는데....

atoi에서 에러가 발생 오버플로우가 발생했다

int형에 담아 낼 수 있는 범위를 넘어섰나보다

그렇게 큰 값은 안나올텐데 이상하게 여기면서도 이럴경우 연산을 짧게 나눠서 반복적으로 돌리면 된다는걸 알기에 수정

그래서 나온게 아래 방식 문자열을 숫자로 바꾸면서 절대 오버플로우 나지않게 짜르려는 숫자 n보다 한글자 크게 잘라서 반복 계산

 1. str을 짤라서 할지 그대로 할지 타겟을 정함 - 짜르는 기준 n의 글자수 + 1 보다 큰가

 2. 정해진 타겟을 atoi로 int형으로 변환

 3. 변환한 값 % n 값을 구함

 4. 정해진 타겟뒤에 str값이 더 있는지 확인함

 5. 더 있으면 나머지값에 추가 문자열을 붙여서 2번 타겟으로 반복

 6. 정해진 타겟뒤에 str값이 없으면 나머지값이 0인지 확인

 7. 나머지값이 0이 아니면 str값에 "1"을 덧붙여서 1번 str로 복귀

 

방법을 보면 아마 가산기에 대해 공부했던사람은 어 이거 반가산기? 뭐 이런 소리가 나올거다 

맞다 그거 생각하고 쓴거다

그렇게 코드로 변환했고 예시 입출력도 다 통과!

그렇게 제출을 했으나....

- 시간 초과

 

평소에 무언가 기능을 만들면 일단 돌아가는게 제일 그다음은 입출력에 대해 안전하게! 이런거만 생각하다 

시간이라는걸 만나니 굉장히 당황했다

과연 코테는 그렇구나 싶다 

분명 학생일때 몇번 경험했을텐데 왜 기억에 없는지 모르겠다

뭐 아무튼 그래서 어떻게 시간을 줄일까 고민하며 이것저것 아이디어를 써봤는데 막상 코드로 짜려니 다 싫어져서 지피티에게 부탁하기로 함....

 

지피티쨩의 해결방안

현재까지 만든 값의 mod 값을 유지한다.
다음 값은 (이전 mod * 10 + 1) % n

 

이거 보고 처음엔 뭔소린가 했는데

r은 나머지

이전 숫자 = k * n + r 라 하면

(이전 숫자 % n) = r

다음 나머지 구하기

(이전 숫자 × 10 + 1) % n
= ((k*n + r) × 10 + 1) % n
= (k*n*10 + r*10 + 1) % n

10kn은 n의 배수라 0

결국 (r * 10 + 1)n만 남게 된다아~

 

마치 방정식 푸는거 마냥 접근하는게 참 신기하고 아 문제 분류제목이 이래서 수학이였구나 라고 깨닫게되었다.

 

뭐 아무튼 그래서 

그런방법으로 통과

#include <stdio.h>

/**
 q4375 1
 */

int solution(int n) {
    int remain = 1 % n;
    int count = 1;
    
    while (remain != 0) {
        remain = (remain * 10 + 1) % n;
        count ++;
    }
    
    return count;
}


int main(int argc, const char * argv[]) {
	int n = 0;
    while (scanf("%d", &n) != EOF) {
        printf("%d\n", solution(n));
    }
    
    return 0;
}

아 참고로 또 while - EOF 처리 안해서 틀렸다고 리젝먹었었다.

 

아래는 깃허브~

https://github.com/wiwi-git/c-baekjoon/

GitHub · Change is constant. GitHub keeps you ahead.