[2007년 1924]첼러의 공식과 음수의 나머지

요일을 구하는 알고리즘 문제를 풀었다.

 

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

쉬운 문제라고 생각했는데, 자꾸 틀려서 계속 생각했다

 

 

우선 첼러의 공식!

 

위키피디아 에 너무 잘나와있어서 따로 적지는 않겠지만,

주의 할점이 1월과 2월 계산은 예외적으로 달+=12와 연도-=1을 해야한다는 것이다!

 

두번째로 챌러 공식에 대한 나머지!

 

챌러 공식을 구하고 나서 %7을 해준다.

그런데 값이 음수가 나올때가 있다.

 

-16%7=???

 

Java로 돌리면 -16%7=-2로 나온다

7*(-2)-2=-16이므로 이렇게 나오는 것 같다.

 

하지만 우리가 보통 알고있는

 

M/N=a----r일떼

N*a+r=M 이다

 

이러한 모습의 나머지 정리는 나머지가 양수임을 조건으로 하는 것이다.

따라서 음수를 나누어서 나머지를 구하려면 양수인 음수가 나오도록 해야한다.

 

그래서 생각한 방법이

 

r=N*(M/N-1)-M을 하는 것이다(단,M<0)

이렇게 하면 java에서는 음수를 나누었을 때 양수의 나머지를 구할 수 있다!

 

요일을 구하는 알고리즘에서도 첼러의 공식에 이러한 방법을 적용하면 올바르게 요일을 구할 수 있다.

 

예시

(2007년이라는 전제,월=x, 일=y)

 

import java.util.Scanner;
public class year20071924 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();        
        int k=(y+(26*(x+1)/10)+07+(07/4)+(20/4)+(-2*20));//첼러의 공식
        if(x==1 || x==2) {
            x+=12;
            k=(y+(26*(x+1)/10)+06+(06/4)+(20/4)+(-2*20));//첼러의 공식
        }
        if(k<0) {
            k=(k/7-1)*7-k;//음수의 나머지 구하기
        }else {
            k%=7;
        }
        switch(Math.abs(k)) {
        case 1:
            System.out.println("SUN");
            break;
        case 2:
            System.out.println("MON");
            break;
        case 3:
            System.out.println("TUE");
            break;
        case 4:
            System.out.println("WED");
            break;
        case 5:
            System.out.println("THU");
            break;
        case 6:
            System.out.println("FRI");
            break;
        case 0:
            System.out.println("SAT");
            break;            
        }
    }
}