선장 일지

• 생각

1. 해당 index와 전 index의 값이 10 이상 26이하면 +1을 또 해준다. (* 0은 무시해야 된다.)

• 코드

정답 코드 : 기존 1개의 문자는 나온다는 가정하에 2글자가 있으면 +1을 더 해주면서 dp배열 돌린다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static String N;
	static long[] dp;

	public static void main(String[] args) throws Exception {
		SetData();
		SaveMaxValue();
		System.out.println(dp[N.length()] % 1000000);
	}

	// 데이터
	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = br.readLine();
		
		// 0으로 시작하는 경우 암호를 해석 할 수 없기 때문에 0을 출력하고 종료해야 된다.
		// 이 부분을 생각 안하고 있다가 애먹었다.
		if (N.charAt(0) == '0') {
			System.out.println(0);
			System.exit(0);
		}

		dp = new long[N.length() + 1];
		dp[0] = 1;
		dp[1] = 1;
	}

	private static void SaveMaxValue() {
		for (int i = 1; i < N.length(); i++) {
			int previousNumber = N.charAt(i - 1) - '0';
			int currentNumber = N.charAt(i) - '0';
			// 1 글자만
			if (currentNumber >= 1 && currentNumber <= 9) {
				dp[i + 1] += dp[i];
			}
			// 2 글자도 가능
			if (!(previousNumber == 0 || previousNumber > 2 || (previousNumber == 2 && currentNumber > 6))) {
				dp[i + 1] += dp[i - 1];
			}

			dp[i + 1] %= 1000000;
		}
	}

}

• 생각

1. 문자 앞 4, 뒤 4를 제외한 문자열만 문자열 배열에 가져와서, a~z개 모든 조합의 6개를 dfs를 통해 돌리면서 확인한다. ==>> 해봤는데 시간초과 뜸.

===>>> 시간초과 뜬 이유는 기존 알파벳 5개를 제외한 나머지 알파벳으로 dfs를 돌려야 했다. (문제 잘못 이해...)

• 코드

정답 코드 : dfs를 통해 K - 5 개의 모든 알파벳 조합을 돌렸다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int maxValue, N, K;
	static String[] s;
	static boolean[] check;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		maxValue = 0;
		s = new String[N];
		check = new boolean[26];

		// 무조건 배워야하는 단어 5개
		check['a' - 'a'] = true;
		check['n' - 'a'] = true;
		check['t' - 'a'] = true;
		check['i' - 'a'] = true;
		check['c' - 'a'] = true;

		// 앞 anta 뒤 tica를 제외한 문자열을 갖고온다.
		for (int i = 0; i < N; i++) {
			String temp = br.readLine();
			s[i] = temp.substring(4, temp.length() - 4);
		}

		dfs(0, 0);
		System.out.println(maxValue);
	}

	private static void dfs(int count, int start) {
		// basecase
		if (count == K - 5) {
			int temp = 0;
			for (int i = 0; i < N; i++) {
				boolean flag = true;

				// 배운 알파벳이 있는지 check
				for (int j = 0; j < s[i].length(); j++) {
					if (!check[s[i].charAt(j) - 'a']) {
						flag = false;
						break;
					}
				}

				if (flag) 
					temp++;				
			}
			maxValue = Math.max(temp, maxValue);
			return;
		}

		for (int i = start; i < 26; i++) {
			if (!check[i]) {
				check[i] = true;
				dfs(count + 1, i);
				check[i] = false;
			}
		}
	}
}

• 생각

1. 배열을 만들어서 지어도 되는 건물 index를 먼저 채워 넣으며 다른 건물을 더 해준다. 이걸 어떻게 구현해야 될 지 찾아보니 이런 상황에서 풀 때 쓰면 좋은 알고리즘을 찾았다. 위상 정렬이라는 알고리즘이다.

위상 정렬 (velog.io/@max9106/Algorithm-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%ACTopology-Sort - 직접 정리해서 링크 바꿔 놓자!) 

- 어떤 일을 하는 순서를 찾는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

- DAG(Directed Acyclic Graph: 사이클이 존재하지 않는 방향 그래프)에만 적용할 수 있다.

• 코드

정답 코드 : 위상 정렬을 큐를 사용하여 구현한 코드이다. 위상 정렬을 처음 접해 보았는데 코드가 깔끔하다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
        int N = Integer.parseInt(br.readLine());
        ArrayList<ArrayList<Integer>> preBuildingNumber = new ArrayList<>();
 
        for (int i = 0; i <= N; i++) {
            preBuildingNumber.add(new ArrayList<>());
        }
 
        int[] indegree = new int[N + 1]; // 특정 건물을 짓기 전에 먼저 지어야 할 건물의 개수
        int[] times = new int[N + 1]; // 특정 건물을 짓는 데 걸리는 시간
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
 
            times[i] = Integer.parseInt(st.nextToken());	// 해당 건물을 짓기 위한 시간
            while (true) {
                int preBuildingNumberTemp = Integer.parseInt(st.nextToken());
 
                if (preBuildingNumberTemp == -1)
                    break;
 
                preBuildingNumber.get(preBuildingNumberTemp).add(i);
 
                indegree[i]++;		// 해당 건물을 짓기 전 지어야 할 건물의 수를 더해준다.
            }
        }
 
        String timeForBuilding = topologicalSort(preBuildingNumber, indegree, times, N);
 
        System.out.print(timeForBuilding);

    }
    
    // 위상 정렬
    public static String topologicalSort(ArrayList<ArrayList<Integer>> a, int[] indegree, int[] times, int N) {
        Queue<Integer> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        
        // 먼저 지어야할 건물이 없는 건물을 큐에 집어 넣음. 해당 큐에 있는 건물을 먼저 짓는다.
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        // 특정 건물을 짓기 전까지 걸린 시간 누적
        int[] result = new int[N + 1];
 
        while (!queue.isEmpty()) {
            int now = queue.poll();
 
            for (int next : a.get(now)) {
                indegree[next]--;
                
                // indegree를 줄여나가는 과정
                // result[next] = max(result[next], result[now] + times[now])
                // 위의 수식을 활용하여 result의 값을 초기화하는 것이 핵심
                result[next] = Math.max(result[next], result[now] + times[now]);
 
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        
        // 특정 건물을 짓기 전 먼저 지어야할 건물의 시간 + 특정 건물을 짓는 시간
        for (int i = 1; i <= N; i++) {
            sb.append((result[i] + times[i]) + "\n");
        }
 
        return sb.toString();
    }
}

• 생각

보자마자 피보나치 수열이 생각 났다. N이 3보다 클땐 해당 인덱스 -1,-2,-3,-4한 값들을 모두 더해주면 된다.

• 코드

정답 코드 : 피보나치와 비슷한 방식이다. 피보나치는 전 index, 전전 index인 2개 수를 더했다면 해당 문제는 전, 전전, 전전전, 전전전전 index의 값을 더 해주면 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long[] array = new long[69];
        array[0] = 1;
        array[1] = 1;
        array[2] = 2;
        array[3] = 4;
        for(int i = 4; i < 68; i++)
            array[i] = array[i - 1] + array[i - 2] + array[i - 3] + array[i - 4];
        
        int t = Integer.parseInt(br.readLine());
        for(int i = 0; i < t; i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(array[n]);
        }
    }
}

• 생각

1. 모든 index를 bfs 메소드로 보내서 가장 긴 max 값을 찾는다 => 시간초과 뜰 것 같다. X

2. dp 배열을 통해 지나온 길은 최장길이가 몇인지 저장해둔다 => 전에 저장되있는 길에 지금 까지 왔던 길이 걸릴 수 있다? => 대나무 개수가 지나온 길은 안걸리게 해줌(그 전 대나무 개수가 더 많아야 되기 때문) => dfs 이용 O

• 코드

정답 코드 : dfs로 배열을 정확하게 돌아주고, dp배열을 통해 시간을 단축시킨다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int[][] array, dp;
	static int[] x = { -1, 1, 0, 0 };
	static int[] y = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		n = Integer.parseInt(br.readLine());
		array = new int[n][n];
		dp = new int[n][n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
			}
		}

        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(dfs(i, j), max);
            }
        }
        System.out.println(max);
    }
 
    static int dfs(int i, int j) {
        // basecase 기존에 저장되있는 dp 값을 return
    	if(dp[i][j] != 0) {
            return dp[i][j];
        }
        
        int count = 1;
        for (int direction = 0; direction < 4; direction++) {
			int r = i + x[direction];
			int c = j + y[direction];
			
            if(r >= 0 && r < n && c >= 0 && c < n) {
                if(array[i][j] < array[r][c]) {
                    count = Math.max(dfs(r, c) + 1, count);
                    // 가장 큰 count 값을 dp에 저장
                    dp[i][j] = count;
                }
            }
        }
        return count;
    }
}

• 코드

정답 코드 : DP문제이다. 현재 index의 상자 크기보다 앞의 index의 상자 크기가 더 작으면 앞의 index의 상자 dp값 + 1 이 현재 dp값보다 크면 변경해준 뒤 max값을 현재 dp값이랑 비교해서 변경해준다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int array[] = new int[N+1];
		int dp[] = new int[N+1];
		int max = 0;
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}

		
		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= i; j++) {
				// 앞에 자신보다 작은 상자가 있으면 dp[j]+1한 값이 현재 i 인덱스보다 클시 dp[i] 변경
				if (array[j] < array[i])
					dp[i] = Math.max(dp[i], dp[j] + 1);
			}
			// 현재 i 인덱스의 dp 값이 max값보다 크면 max값을 dp[i]로 변경
			max = Math.max(max, dp[i]);
		}

		// 기존에 있던 상자 + 1
		System.out.println(max+1);
	}
}

• 코드

정답 코드 : 행렬이 뭉쳐있는 묶음 수와 묶음 덩어리의 개수를 파악하는 문제이다.

               FOR문을 통해 첫번째 묶음의 위치를 알아내면 BFS로 근처에있는 1의 개수를 모두 더 해준 다음 return해주는 방식을 사용하였다.

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Arrays;
import java.util.ArrayList; 
import java.util.Collections;

class Main {
	static int[] x = {-1, 1, 0, 0};
    static int[] y = {0, 0, -1, 1};
	static boolean[][] check;
	
  private static void solution(int sizeOfMatrix, int[][] matrix) {
    // TODO: 이곳에 코드를 작성하세요.
		check = new boolean[sizeOfMatrix][sizeOfMatrix];
		int count = 0;
		ArrayList<Integer> al = new ArrayList<Integer>();
		
		for(int i = 0; i < sizeOfMatrix; i++) {
			for(int j = 0; j < sizeOfMatrix; j++) {
				// 덩어리 묶음의 처음 발견된 index
				 if(matrix[i][j] == 1 && !check[i][j]) {
					  count++;
					 	check[i][j] = true;
					  al.add(bfs(sizeOfMatrix, matrix, i , j));
				 }
			}
		}	
		Collections.sort(al);
																			
		System.out.println(count);
		for(int value : al)
				System.out.print(value + " ");
  }
	
	//덩어리의 첫번쨰 index를 통해 주변에 몇개의 덩어리가 있는지 파악 후 return
	private static int bfs(int size, int[][] array, int i, int j) {        
     	Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {i,j});
				
		int sum = 1;
        while(!queue.isEmpty()){
        	int location[] = queue.poll();

         	for(int direction = 0; direction < 4; direction++){
            	int r = location[0] + x[direction];
            	int c = location[1] + y[direction];

        	    if(r >= 0 && c >= 0 && r < size && c < size) {
              	  if(array[r][c] == 1 && !check[r][c]) {
                 		check[r][c] = true;
						sum++;
       		            queue.add(new int[] {r,c});
                  }
  	            }
            }
		 }
		 return sum;
	}
}

• 맞을 결과

• 코드

정답 코드 : Chained Matrix라는 개념을 통해 점화식으로 구현한 코드이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {	
    static int[][] dp;
    static int[][] array;
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        dp = new int[N][N];
        array = new int[N][2];
        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            array[i][0] = Integer.parseInt(st.nextToken());
            array[i][1] = Integer.parseInt(st.nextToken());
        }


        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(i==j)
                    dp[i][j]=0;
                else
                    dp[i][j]=Integer.MAX_VALUE;
            }
        }

        for(int i=1;i<N;i++){
            for(int j=0;j+i<N;j++){
                setDP(j,j+i);
            }
        }
        System.out.println(dp[0][N-1]);
    }

    private static void setDP(int start, int end) {
        for(int i=start;i<end;i++){
            int sum = dp[start][i] + dp[i+1][end] + array[start][0]*array[i][1]*array[end][1];
            dp[start][end] = Math.min(sum,dp[start][end]);
        }
    }
}