글 읽기 - 2775번은 파스칼의 삼각형으로 환원됩니다.

chun92 3년 전 3

처음엔 memoization으로 문제를 풀까 생각해봤지만, 가만히 보면 이 문제는 combination 문제로 환원됩니다.

만약 -1층이 있다고 가정하고 그림을 그리면

3층 1 5 15 35 70 ...

2층 1 4 10 20 35 56 ...

1층 1 3 6 10 15 20 28 ..

0층 1 2 3 4 5 6 7 8 9 ..

-1층 1 1 1 1 1 1 1 1 1 1 ....

a층 b호를 (a,b)로 표기했을 때,
a+b의 합을 기준으로 수를 나열하면 다음과 같은 규칙을 찾을 수 있습니다.

-1: 1
1: 1 1
2: 1 2 1
3: 1 3 3 1
4: 1 4 6 4 1
5: 1 5 10 10 5 1

이는 파스칼의 삼각형으로 환원되며, 각 항은 combination(조합)으로 나타낼 수 있습니다.
https://ko.wikipedia.org/wiki/...

아래는 예제 코드입니다.
도움이 되면 좋겠습니다.

package main

import (
	"bufio"
	"os"
	"strconv"
)

func main() {
	in := bufio.NewScanner(os.Stdin)
	out := bufio.NewWriter(os.Stdout)

	in.Split(bufio.ScanWords)
	in.Scan()
	c, _ := strconv.Atoi(in.Text())

	for i := 0; i < c; i++ {
		in.Scan()
		n, _ := strconv.Atoi(in.Text())
		in.Scan()
		k, _ := strconv.Atoi(in.Text())

		n = n + 1
		k = k - 1

		res := combination(n+k, k)
		out.WriteString(strconv.Itoa(res) + "\n")
	}
	out.Flush()
}

func combination(n, r int) int {
	if n == r || r == 0 {
		return 1
	} else {
		return combination(n-1, r-1) + combination(n-1, r)
	}
}

rhsnfl1122 3년 전 0

머리 끙끙 싸매고 있었는데 좋은 답변이 되었습니다

jkim67cloud 3년 전 0

아 ㅜㅜㅜ 너무감사합니다 ~~ !!!!!

행복하십쇼

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

문제

문제

출처

ICPC

2775번은 파스칼의 삼각형으로 환원됩니다.

chun92 3년 전 3

rhsnfl1122 3년 전 0

jkim67cloud 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말