문제풀이 - java 백준 6064 카잉달력

문제

 

 

 

 

 

카잉다력은 x,y값인 <1,1> 년부터 시작해서 <2,2> <3,3> .. 식으로 해가 흐른다.
최대 해가 정해져있는데 예를들어 M, N이 <10,12>면 x ,y가 <10,10> 까지 증가하다가 M의 최대치인 10 다음부터 1로 바뀌면서 <1,11> 로 진행된다.

문제: m, n , x, y 를 입력한 후 < m,n > 달력에서 < x, y> 인 해가 몇번째인가??

 

풀이

 

 

처음 풀었을 때:

m,n,x,y를 차례로 입력받고 while(true) 문으로 무한 반복을 한다.
int startx, starty 변수를 0부터 시작하여 한바퀴 돌때마다 ++ 시켜주고 이 startx, starty 가 m,n 이 도달 했을 때 각각 1로 초기화 시켜주어서 1부터 세게 만들었다.
그리고 처음 목표했던 x , y에 도다르면 그때의 count 변수(while문 한바퀴 돌때마다 ++ 되는) 를 출력해 주었다.
while문을 돌다가 목표한 x, y값이 없을때: <1,1> 로 시작했기 때문에 다시 startX와 startY가 1,1 이 되면 한바퀴돌아도 값이 없다고 판단하여 count: -1 로 초기화 해주고 break;한다.

 

import java.util.Scanner;

public class Baekjoon_6064 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int m, n;
    int x, y;
    int startX = 0;
    int startY = 0;
    int count = 0;
    boolean first = false;

    int num = sc.nextInt();


    for (int i = 0; i < num; i++) { // num번 반복
    m = sc.nextInt();
    n = sc.nextInt();
    x = sc.nextInt();
    y = sc.nextInt();
    while (true) {
      count++;			//한바퀴 돌때마다, 변수들이 +1 씩된다.
      startX++;
      startY++;

      if (startX == m + 1) { // startX가 증가할 때 m 이되면 1로 초기화
        startX = 1;
      }
      if (startY == n + 1) { // startY가 증가할 때 n 이되면 1로 초기화
        startY = 1;
      }

      if ((startX == 1 && startY == 1)&&first) { 
      // while문 돌다가 다시 1, 1 이 되면 종료
      // first는 이게 첫번째 <1,1>인지 판단하는 boolean 변수로 첫 <1,1>이
      // 지나면 first는 true 로 초기화되기 때문에 if 문이 실행된다.
        count = -1;
        break;
      }

      if (startX == x && startY == y) {
        break;
      }

      first = true;


    }
    System.out.println(count);
    startX = 0;
    startY = 0;
    count = 0;
    first = false;
    }


  }
}

 

근데 이렇게 해주니까 시간초과가 뜬다. while문을 이용해서 처음부터 돌려주니까 너무많은 반복때문에 시간초과 인듯 하다.

 

ex M=5, N=7
1: <1,1> 6: <1,6> 11<1,4> 16<1,2> 21<1,7> 26<1,5> 31<1,3>
2: <2,2> 7: <2,7> 12<2,5> 17<2,3> 22<2,1> 27<2,6> 32<2,4>
3: <3,3> 8: <3,1> 13<3,6> 18<3,4> 23<3,2> 28<3,7> 33<3,5>
4: <4,4> 9: <4,2> 14<4,7> 19<4,5> 24<4,3> 29<4,1> 34<4,6>
5: <5,5> 10:<5,3> 15<5,1> 20<5,6> 25<5,4> 30<5,2> 35<5,7>

 

위와 같이 M=5, N=7 이면은 x 기준으로 M번 째일때마다 x 는 그대로고 y값만 바뀐다. 그러므로
반복 for문을 for (int i = x; i < (m * n); i += m) 으로 주었다.
우리는 < x, y > 가 몇번째인지 구해야하므로 i = x 로 시작한다.
최대 M * N = 35 개가 나올 수있으므로 최대 35까지 돌린다.
i+=m 에서 x는 m만큼 더해줘도 그대로이므로 m만큼 + 해준다
if (i % n == y) { 조건을 걸어주어서 y 의 최대반복인 n만큼 % 해준다.
우리가 구할 y 값이나오면 break;

 

import java.util.Scanner;

public class Baekjoon_6064_1 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int m, n;
    int x, y;
    int num = sc.nextInt();
    boolean tf = false;


    for (int j = 0; j < num; j++) { // num: 횟수
      m = sc.nextInt();
      n = sc.nextInt();
      x = sc.nextInt()-1;    // %연산이 0일 수있기때문에 -1 해준다.
      y = sc.nextInt()-1;    // %연산이 0일 수있기때문에 -1 해준다.

      for (int i = x; i < (m * n); i += m) { 
      
        if (i % n == y) {  
        // %연산은 0이 나올 수있다. 
        // 만약 i%n == 0 이면 y값은 1이상이므로 if에걸릴수가없다 .
        // 그래서 x-1, y-1 해준다. 만약 y가 1이면 0이됨
      
          System.out.println(i+1); // 출력할때 +1 해준다.
          tf = true;
          break;
        }
      }
      if (!tf) {
        System.out.println(-1);
      }
      tf = false;
    }

  }
}

 

 

회고

 

실버1등급 문제이다. 나한텐 어렵다. 처음풀었을때 알고리즘밖에 난 생각이 안난다. 그래서 다른 블로그를 참고해서 공부했다.
어떻게 저런생각이 날 수 있는지 궁금하다.
경우의 수들을 나열하고 규칙을 찾는것이 중요한것 같다. 규칙을 찾고 연사자를 사용해서 간단히 하는 연습을 해봐야겠다.

 

참고:
https://1-7171771.tistory.com/38