본문 바로가기

SWEA/D2

[SWEA 2005][D2][JAVA] 파스칼의 삼각형

[문제]

 

크기가 N인 파스칼의 삼각형을 만들어야 한다.

파스칼의 삼각형이란 아래와 같은 규칙을 따른다.

1. 첫 번째 줄은 항상 숫자 1이다.

2. 두 번째 줄부터 각 숫자들은 자신의 왼쪽과 오른쪽 위의 숫자의 합으로 구성된다.

 

 

[풀이방법]

 

(0,0)

(1,0) (1,1)

(2,0) (2,1) (2,2)

(3,0) (3,1) (3,2) (3,3)

 

(0,0)을 기준으로 왼쪽은 x좌표만 1씩 증가하는 좌표와, 오른쪽은 x와 y가 동일한 좌표는 모두 1입니다. 

이 특징을 이용해서 (i, j)라고 한다면

  • j == 0 일 때 (i+1, j)는 1
  • i == j 일 때 (i+1, j+1)은 1
  • 그 외에는 (i, j) 는 (i-1, j-1) + (i-1, j)의 합 

for (int i = 0; i < N; i++) {

    for (int j = 0; j <= i; j++) {

        if (i == j) 

            triangle[i][j] = 1;

                    

        else if (j == 0) 

            triangle[i][j] = 1;

                    

        else 

            triangle[i][j] = triangle[i-1][j] + triangle[i-1][j-1];

            

    }

}