[Codeforces] 509A: Maximum in Table

https://codeforces.com/problemset/problem/509/A

Problem - 509A - Codeforces

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[][] arr = new int[n][n];
		if(n == 1) {
			System.out.println(1);
			return;
		}
			// 1행의 값들은 1 ... 0,0 ~ 0,n = 1
			for(int i=0; i<1; i++)
				for(int j=0; j<n; j++)
					arr[i][j] = 1;
			
			// i행의 첫번째 열은 모두 1 ... (0,0) , (1,0) ~ (n,0) = 1
			for(int i=0; i<n; i++)
				for(int j=0; j<1; j++)
					arr[i][j] = 1;
			
			// 위에서 제외한 나머지 행은 규칙에 따라 저장
			for(int i=1; i<n; i++) 
				for(int j=1; j<n; j++)
					arr[i][j] = arr[i-1][j] + arr[i][j-1];
		
		// 항상 마지막 값이 젤 큼
		System.out.println(arr[n-1][n-1]);
		scan.close();
	}

}

풀이

문제에서 주어진 조건은 다음과 같다

첫번째 행과 첫번째 열들은 1이다.

그 외의 행열들은 다음 조건을 만족한다. arr[i][j] = arr[i-1][j] + arr[i][j-1]

 

따라서 위 조건을 그대로 첫번째 행들을 1로 설정한다.

			for(int i=0; i<1; i++)
				for(int j=0; j<n; j++)
					arr[i][j] = 1;

 

그 후 모든 행의 첫번째 열들을 1로 설정한다.

			for(int i=0; i<n; i++)
				for(int j=0; j<1; j++)
					arr[i][j] = 1;

 

나머지 행, 열들은 규칙에 따라 설정한다.

			for(int i=1; i<n; i++) 
				for(int j=1; j<n; j++)
					arr[i][j] = arr[i-1][j] + arr[i][j-1];

 

가장 큰 값은 가장 마지막 인덱스의 값이므로 arr[n-1][n-1] 을 출력한다.