83 | Notion

<aside> 💛

1947

</aside>

import java.util.Scanner;
public class Practice83 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		long mod = 1000000000;
		long D[] = new long[1000001];
		D[1] = 0;
		D[2] = 1;
		
		for(int i = 3; i <= N; i++) {
			D[i] = (i - 1) * (D[i - 1] + D[i - 2]);
		}
		System.out.println(D[N] % mod);
		
		sc.close();
	}

}

→ 안돌아감

import java.util.Scanner;
public class Practice83 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		long mod = 1000000000;
		long D[] = new long[1000001];
		D[1] = 0;
		D[2] = 1;
		
		for(int i = 3; i <= N; i++) {
			D[i] = (i - 1) * (D[i - 1] + D[i - 2]) % mod;
		}
		System.out.println(D[N]);
		
		sc.close();
	}
}

→ 돌아감

사유

	실패하는 코드	성공하는 코드
계산 방식	모든 계산을 끝낸 후 마지막에 1번 나머지 연산	계산 과정 중간중간에 계속 나머지 연산
문제점	N이 커지면 중간 계산 결과가 `long`의 범위를 초과하여 오버플로우 발생	중간 결과 값을 계속 `mod`보다 작은 수로 유지시켜 오버플로우를 방지
결과	오버플로우로 인해 완전히 잘못된 최종 값 도출	모듈러 연산의 성질에 따라 수학적으로 올바른 최종 값 도출