본문 바로가기

PS

[BOJ]2526번 : 싸이클

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

 

2526번: 싸이클

두 자연수 N과 P를 가지고  다음 과정을 거쳐서 나오는 숫자들을 차례대로 출력해보자. 처음 출력하는 숫자는 N이고, 두 번째 이후 출력하는  숫자들은 N을 곱하고 P로 나눈 나머지를 구하는 과

www.acmicpc.net

 

분류 : 없음

 

더보기
public class Main {

    public static PrintWriter out;
    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        int N = sc.nextInt();
        int P = sc.nextInt();
        Vector<Integer> v = new Vector<Integer>();
        Vector<Integer> rv = new Vector<Integer>();
        int temp = N;
        for(int i=0;i<1000;i++)
        {
            temp = (temp*N)%P;
            
            if(v.contains(temp) && !rv.contains(temp)){
                rv.add(temp);
            }
            v.add(temp);    
        }
        out.println(rv.size());
        out.flush();
    }
}

 

문제는 되게 길지만 결국은 사이클을 이루는 서로 다른 숫자가 몇 개 인가? 하는 문제이다.

 

Vector v 는 계산과정에서 일어나는 모든 수를 집어넣는 벡터, Vector rv는 사이클을 이루는 수를 집어넣는 벡터이다.

 

대략 1000번쯤이면 모든 경우를 해결할수 있지 않을까? 하는 생각에 for문을 1000번까지 돌렸고 , 다행하게도 통과했다.

 

사실 저 부분은 예외 상황이 발생할 수 있는 부분이라 고쳐야 할 것 같긴 하다.

 

그러고 나서 마지막에 rv의 사이즈를 출력하면 사이클을 이루는 수의 개수를 구할 수 있다.

'PS' 카테고리의 다른 글

[BOJ] 1051번 - 숫자 정사각형  (0) 2017.05.29
[BOJ] 2512번 - 예산  (0) 2017.05.29
[BOJ]1660번 : 캡틴 이다솜  (0) 2017.04.26
[BOJ]5052번 : 전화번호 목록  (0) 2017.04.24
[BOJ]8983번 : 사냥꾼  (0) 2017.04.22