개발 블로그

문제 링크 : https://acmicpc.net/problem/15989

3
4
7
10

4
8
14

풀이 방법

[1]

1

=> 1가지

(0가지 일 수도 있는지?...)

[2] 

1 + 1

=> 1가지

[3]

1 + 1 + 1

2 + 1

=> 2가지

[4]

1 + 1 + 1 + 1

2 + 1 + 1 , 2 + 2

3 + 1

=> 4가지

[5]

1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 , 2 + 2 + 1

3 + 1 + 1, 3 + 2

=> 5가지

[6]

1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 , 2 + 2 + 1 + 1, 2 + 2 + 2

3 + 1 + 1 + 1, 3 + 2 + 1

3 + 3

=> 7가지

[7]

1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1 , 2 + 2 + 1 + 1 + 1, 2 + 2 + 2 + 1

3 + 1 + 1 + 1 + 1, 3 + 2 + 1 + 1, 3 + 2 + 2, 

3 + 3 + 1

=> 8가지

[8]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1), (2 + 2 + 2+ 2)

(3 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1), (3 + 2 + 2 + 1)

(3 + 3 + 1 + 1), (3 + 3 + 2)

=> 10가지

 [9]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1)

(3 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1), (3 + 2 + 2 + 2)

(3 + 3 + 1 + 1 + 1), (3 + 3 + 2 + 1)

(3 + 3 + 3)

=> 12가지

 [10]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1), (2 + 2 + 2+ 2 + 2)

(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1 + 1), (3 + 2 + 2 + 2 + 1)

(3 + 3 + 1 + 1 + 1 + 1), (3 + 3 + 2 + 1 + 1), (3 + 3 + 2 + 2)

(3 + 3 + 3 + 1)

=> 14가지

 [11]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 2 + 1)

(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 2 + 1 + 1), (3 + 2 + 2 + 2 + 2)

(3 + 3 + 1 + 1 + 1 + 1 + 1), (3 + 3 + 2 + 1 + 1 + 1), (3 + 3 + 2 + 2 + 1)

(3 + 3 + 3 + 1 + 1), (3 + 3 + 3 + 2)

=> 16가지

6부터 2씩 증가-> fail!!!

==========================

dp[n,k] : 1,,,k 를 활용해 n을 만드는 방법의 수로 가정하고 각 값을 구해보자. 

===========================================

• dp[n,1] = 1
• dp[n,2] = n/2(몫만) + 1
• dp[n-3] = dp[n-1, 1] +dp[n-2, 2] + dp[n-3, 3]   = 1 + {(n-2)/2} + 1 + dp[n-3,3]

import java.util.Scanner;

public class BOJ_15989_123더하기4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[][] dp= new int[10001][4];

        for(int n = 0; n<=10000; n++){
            dp[n][0] = 0;
            dp[n][1] = 1;
            dp[n][2] = n/2 + 1;
        }
        dp[1][2] = 1; dp[1][3] = 1;
        dp[2][2] = 1; dp[2][3] = 2;
        dp[3][2] = 2; dp[3][3] = 3;
        dp[4][2] = 3; dp[4][3] = 4;
        
        for(int i = 5; i<=10000; i++){
            dp[i][3] = 2 + (i-2)/2 + dp[i-3][3];
        }


        int n;
        for(int i = 0; i<T; i++){
            n = sc.nextInt();
            System.out.println(dp[n][3]);

        }
    }
}

문제 링크 : https://www.acmicpc.net/problem/16234

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

접근 방법

각 땅 (r,c) 에 대해 무한루프를 돌면서 

     - BFS를 이용해 국경선을 서로 열 수 있는 땅을 Queue에 다 넣고, BFS 탐색이 끝나면 인구이동을 해준다. 

     - 모든 칸에 대해 인구이동 여부를 탐색 했으면 다시 처음으로 돌아가서 visited를 초기화 시킨 후 재 탐색한다. (만약 이 단계에서 탐색이 끝났을 때 인구이동이 한 번도 발생하지 않았다면 무한루프를 종료시킨다.)

import java.util.*;

class Pair16234{
	Integer r, c;
	public Pair16234(Integer _r, Integer _c) {
		this.r = _r;
		this.c = _c;
	}
	public int getRow() {
		return this.r;
	}
	public int getCol() {
		return this.c;
	}
	
}
public class SM_BOJ16234_인구이동 {

	static int N, L, R, answer;
	static int[][] map, visited; 
	static int[] dr,dc;

	static boolean chk(int a, int b) {
		int sub = Math.abs(a-b);
		if(L <= sub && sub <=R) return true;
		else return false;
	}
	
	static boolean BFS(int r, int c) {
		
		Queue<Pair16234> que = new LinkedList<Pair16234>();
		ArrayList<Pair16234> vec = new ArrayList<Pair16234>();
		int sum = 0;
		
		Pair16234 p = new Pair16234(r,c);
		que.add(p);
		vec.add(p);
		sum = map[r][c];
		
		while(!que.isEmpty()) {
			Pair16234 pair = que.poll();
			int cr = pair.getRow();
			int cc = pair.getCol();
			
			visited[cr][cc] = 1;
			
			for(int i = 0; i<4; i++) {
				int nr = cr + dr[i];
				int nc = cc + dc[i];
				if(nr<1 || nr>N || nc<1 || nc>N || visited[nr][nc]==1) continue;
				
				if(chk(map[cr][cc], map[nr][nc])) {
					visited[nr][nc] = 1;
					Pair16234 p_next = new Pair16234(nr,nc);
					que.add(p_next);
					vec.add(p_next);
					sum += map[nr][nc];
				}
			}
		}
		
		if(vec.size()==1) {
			visited[vec.get(0).getRow()][vec.get(0).getCol()] = 0;
			return false;
		}
		else {
			int avg = sum / vec.size();
			for(int i = 0; i<vec.size(); i++) {
				int row = vec.get(i).getRow();
				int col = vec.get(i).getCol();
				map[row][col] = avg;
			}
			return true;
		}
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		dr = new int[4];
		dc = new int[4];
		dr[0] = -1; dr[1] = 0; dr[2] = 1; dr[3] = 0;
		dc[0] = 0; dc[1] = 1; dc[2] = 0; dc[3] = -1;

		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();
		
		map = new int[51][51];
		visited = new int[51][51];
		for(int i = 1; i<=N; i++) {
			for(int j = 1; j<=N; j++) {
				map[i][j] = sc.nextInt();
				visited[i][j] = 0;
			}
		}
		
		answer = 0;

		int cnt = 0;	
		while(true) {
			
			if(cnt==N*N) break;
			cnt = 0;
			
			boolean flag = false;
			
            //인구 이동 끝나고 초기화 
			for(int r = 1; r<=N; r++) {
				for(int c = 1; c<=N; c++) {
					visited[r][c] = 0;
				}
			}
			
			for(int i = 1; i<=N; i++) {
				for(int j = 1; j<=N; j++) {

					if(visited[i][j]==0) {
						boolean res = BFS(i,j);		//국경선 열렸으면 true 
						if(res) {
							flag = true;
						}					
						else cnt++;
					}
				}
			}
			
			if(flag) answer++;
		}
		System.out.println(answer);
	}

}