[백준] code.plus(수학,JAVA)4375번, 1

문제 링크

4375번: 1

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

처음 문제를 읽을 때에는 문제 자체가 이해가 되지 않았습니다.

1로만 이루어진 n의 배수를 찾는 것이 핵심이었습니다.1로만 이루어지려면 숫자가 1, 11, 111, 1111, 11111......으로 이루어지고 n의 나눠져야 합니다.

해결 알고리즘은

1. 1,11,111,1111... 을 구합니다.2. 위에 값이 n에 나머지가 0이 되도록 나눠지는지 확인합니다.3. 나눠지면 반복을 종료하고 자릿수를 저장한 변수를 반환하여 결과에 저장합니다.4. 결과를 출력합니다.

 

※ temp = (temp * 10 + 1) % N을 한 이유는 temp가 자릿수가 int범위를 넘어가서 오류가 발생할 수 있으므로 모듈러 산술을 이용하여 나머지를 구하였습니다.모듈러 연산은 

(a+b) mod p = (a mod p + b mod p) mod p

(a-b) mod p = (a mod p - b mod p) mod p

(a*b) mod p = (a mod p * b mod p) mod p

temp mod N = (temp * 1) mod N = (temp mod N * 1 mod N) mod N = (temp mod N) mod N

위에 형식대로 사용할 수 있습니다.

모듈러 산술 - 위키백과, 우리 모두의 백과사전

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 최소 자릿수을 구하는 one함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 최소 자릿수 값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• one에서는 반복문을 통해 위에 해결 알고리즘대로 설계하여 작성하였습니다.

 

결과 코드

import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferdWriter
        //----------입력값 저장 및 함수 실행---------
        String text;
        while((text=br.readLine())!=null) {
        	int N = Integer.parseInt(text);	//입력값 저장
        	int result = one(N);		//함수실행
        	bw.write(result + "\n");	//결과 BufferedWriter에 저장
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //-----------1로 이루어진 수열중 나누어 떨어지는 자릿수 얻는 함수----------
    public static int one(int N) {
    	int temp = 1;
    	int count = 1;	//자릿수 변수
    	for(;;) {
    		if(temp % N ==0)	//나누어 떨어질 때
    			break;
    		temp = (temp * 10 +1) % N;
    		count++;
    	}
    	return count;
    }
}