글 읽기 - 질문있습니다 . 이문제 이런접근 방식으로는 못푸나요?

redbin0471 4년 전 0

nCk 는 n!/(k!*(n-k)!) 인걸로 알고 있습니다.

그러면 n*(n-1)*(n-2)* ... 1 인데 매번 곱에 나머지값을 구하고 k! (n-k)! 도마찬가지로 계산해주면

O(N + K+ N-K) 시간에 구할수 있지않을까 생각해보았습니다.

곱셈에 대해서는 나머지연산이 적용되지않나요 ??

package day0301;

import java.util.Scanner;

public class B11401 {
	static long dp[][];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();

		long Answer = 1L;
		
		for (int k = 0; k < K; k++) {
			Answer = (Answer * (N - k)) % 1000000007;
		}
		
		for(int k=K;k>=2;k--) {
			Answer = (Answer/k);
		}
		
		System.out.println(Answer);
	}
}

redbin0471 4년 전 0

해결했습니다.

공부가 부족했네요 나머지 연산에 대해서는 mod 가 적용되지가 안네요 해보니깐 알수있었습니다 .

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

질문있습니다 . 이문제 이런접근 방식으로는 못푸나요?

redbin0471 4년 전 0

redbin0471 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말