선장 일지

• 생각

보자마자 피보나치 수열이 생각 났다. 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]);
        }
    }
}

• 코드

정답 코드 : Node 클래스를 이진 검색 트리에 맞게 left, right, value를 선언해서 사용했다. 기준 노드보다 삽입 노드의 숫자가 작은 경우 왼쪽, 큰 경우 오른쪽으로 재귀 호출하며 삽입하였고, 출력은 (왼쪽-오른쪽-루트) 순서로 노드를 방문하며 출력하였다.

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));
		int N = Integer.parseInt(br.readLine());

		Node node = new Node(N);
		String s;
		while ((s = br.readLine()) != null) {
			N = Integer.parseInt(s);
			node = InsertNode(node, N);
		}
		
		PostOrder(node);
	}

	private static Node InsertNode(Node node, int N) {
		Node newNode = null;
		if (node == null) 	return new Node(N);

		if (node.value > N) {
			newNode = InsertNode(node.left, N);
			node.left = newNode;
		} 
		else {
			newNode = InsertNode(node.right, N);
			node.right = newNode;
		}
		
		return node;
	}

	private static void PostOrder(Node node) {
		if (node != null) {
			PostOrder(node.left);
			PostOrder(node.right);
			System.out.println(node.value);
		}
	}
	
	private static class Node {
		Node left;
		Node right;
		int value;

		public Node(int value) {
			this.value = value;
		}

	}
}

• 코드

정답 코드 : 그리디 알고리즘 문제이다. 1시간동안 여러가지 방법으로 고민해보았는데 시간안에 풀 수 있는 뚜렷한 방법이 생각나지 않았다...(ㅠㅠ)

그래서 코드를 찾아본 결과 

현재 올리려는 저울추의 무게가, 지금까지 올린 저울추의 총합보다 커지면 저울추의 총합은 측정할 수 없는 최솟값이다.

현재까지 오름차순으로 정렬된 배열을 순서대로 더해준 값+1보다 해당 index의 값이 크면 그 전의 더해준 값들로는 구할 수 없다는 것이 결론이다.

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

public class Algorithm {

	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];

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

		// 무게 순으로 정렬
		Arrays.sort(array);

		int sum = 0;
		for (int i = 0; i < N; i++) {
			if (sum + 1 < array[i]) {
				break;
			}
			
			sum += array[i];
		}

		System.out.println(sum + 1);
	}
}

• 코드

정답 코드 : 처음 사전순으로 정렬 한다음 String에 추가 or 추가하지 않으면서 메소드를 계속 돌림 길이가 L이되면 basecase로 모음 1개이상 자음 2개이상이 되면 출력.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {	
	static char[] array;
	static int L, C;
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		array = new char[C];

		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < C; i++) {
			array[i] = st.nextToken().charAt(0);		
		}
		Arrays.sort(array);		// 핵심 (사전순으로 알파벳이 증가해야되는데 정렬해줌으로 써 알파벳 순으로만 들어가게함)
		
		IncreasedString("", 0);
	}
	
	private static void IncreasedString(String s, int index) {
        if(s.length() == L){ // 길이가 L개 이고
            if(isPossible(s)){ // 모음하나이상, 자음 2개이상 맞으면
                System.out.println(s); // 출력
            }
            return;
        }
        if(index >= C ){ // index 값이 맨끝에 왔으면 종료
            return;
        }        

       	IncreasedString(s + array[index], index + 1);// 자기자신과 다음 문자까지 같이
        IncreasedString(s, index+ 1);// 자기자신만
	}
	
	// 자음 2개이상, 모음 1개 이상인지
    private static boolean isPossible(String s){
        int vowel = 0, consonant = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if(isCollection(s.charAt(i))){
                vowel++;
            }else {
                consonant++;
            }
        }
        return vowel>=1 && consonant >=2;
    }
	
    // 모음인지
	private static boolean isCollection(char c) {
		if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
			return true;

		return false;
	}
}