선장 일지

• 코드

정답 코드 : 기존 연속합 문제에서 다른 점은 최소값 수 하나를 제거할 수 있다는 점! 그래서 기존 연속합 코드에서 DP하나를 더 추가해 최소값을 하나 제외했을 때의 최대값도 유지시켜 주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

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

        int n = Integer.parseInt(br.readLine());
        int[] array = new int[n];
        int [] dp = new int[n];
        int [] dp2 = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) 
        	array[i] = Integer.parseInt(st.nextToken());
        
       
        dp[0] = array[0];
        dp2[0] = array[0];
	    int max = array[0];
	    for(int i=1; i<n; i++){
	    	 dp[i] = Math.max(dp[i-1] + array[i], array[i]);
	    	 dp2[i] = Math.max(dp2[i-1] + array[i], dp[i-1]);
	         
	         max = Math.max(max, Math.max(dp[i],dp2[i]));
	    }

	    System.out.println(max);
    }
}

• 코드

정답 코드 : 처음 P의 길이만큼 넣고 같지않을때 같을때까지의 문자열의 길이 -1을 빼줘서 copy개수를 맞춤. 그 다음 i가 p의길이만큼 됐을때가 처리가 안되서 추가시켜주엇다.

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String S = br.readLine();
		String P = br.readLine();
		
		String temp="";
		int count=P.length();
		
		for(int i=0;i<P.length();i++) {
			temp+=P.charAt(i);
			if(i==P.length()-1 && S.contains(temp))
				count-=temp.length()-1;
			if(!S.contains(temp)) {
				if(temp.length()>2)
					count-=temp.length()-2;
				temp=P.charAt(i)+"";
			}
		}
		System.out.println(count);
	}
}

• 코드

실패 코드 : factorial구해주는 것만 메소드를 만들어서 구해준 뒤 이항계수를 계산해 % 1000000007로 나머지 출력해주었다. 결론은 런타임에러....

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		long N = Integer.parseInt(st.nextToken());
		long K = Integer.parseInt(st.nextToken());
		
		System.out.print((int)(Factorial(N)/(Factorial(K)*Factorial(N-K))% 1000000007));
	}
	
	private static long Factorial(long number) {
	    long factorialNumber = 1;
	    for(int i=2;i<=number;i++)
	    	factorialNumber = factorialNumber*i;
	    return factorialNumber;
	}
}

• 코드

정답 코드 : 이분 탐색을 통해 푼 코드이다. 자세한 설명은 밑에

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	private static long N;
	private static long k;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Long.parseLong(br.readLine());
		k = Long.parseLong(br.readLine());
		
        long left = 1, right = k;
        long printValue = 0;
        
        // 이분 탐색 수행
        while (left <= right) {
            long mid = (left + right) / 2;
            long cnt = 0;
            
            // mid보다 작거나 같은 수는 몇 개인지 계산.
            for (int i = 1; i <= N; i++) {
                cnt += Math.min(mid/i, N);
            }
 
            if (cnt < k) {
                left = mid + 1;
            } else {
            	printValue = mid;
                right = mid - 1;
            }
        }
		
		System.out.print(printValue);
	}
}

• 설명

만약, N이 3이라 할때 A배열이다. B 배열은 (1,2,2,3,3,4,6,6,9)순서가 될 것이다.

예를들어, 4가 B배열의 몇번째 인지 찾는다고 볼때 0번째 열은 4이하가 3개, 1열은 2개, 2열은 1개이다.

총 개수는 6개이고  실제로 4는 6번째 오는 수 였습니다.

이 부분에서

count = Math.min(mid/i,N)  (i는 i번째 열을 의미)

즉, 이 식을 세운 순간부터 우리가 할 일은 1가지로 줄어들게 됩니다.

left = 1, right = K로 두고, left <= right일 때까지 while문을 진행하면서 위 식에 따라서 cnt를 계산한 후, cnt와 K를 비교하면서 left 혹은 right를 초기화하는 것입니다.

• 코드

정답 코드 : 기존 N과 M (11)의 코드에서 StringBuilder에 추가하는 곳에서 오름차순의 형태의 수만 추가해줄 수 있게 boolean을 만들어주었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	private static int list[];
	private static int listvalue[];
	private static int n, m;
	private static StringBuilder sb;

	private static void dfs(int cnt) {
		if (cnt == m) {
			boolean check = true;
			for (int i = 1; i < m; i++) {
				if(list[i-1]>list[i])
					check = false;
			}
			if(check) {
				for (int i = 0; i < m; i++) {
					sb.append(list[i]).append(" ");
				}
				sb.append("\n");
			}
			return;
		}

		int saveValue=-1;
		for (int i = 1; i <= n; i++) {
			if (saveValue==listvalue[i-1])
				continue;
			list[cnt] = listvalue[i - 1];
			saveValue = listvalue[i - 1];
			dfs(cnt + 1);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		list = new int[9];
		listvalue = new int[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			listvalue[i] = Integer.parseInt(st.nextToken());
		sb = new StringBuilder();
		Arrays.sort(listvalue);

		dfs(0);

		bw.write(sb.toString());

		bw.close();
		br.close();
	}

}

• 코드

정답 코드 : 기존 N과 M (10) 문제에서 visit변수가 한줄에 같은 숫자가 반복되지 않게 해주는 변수였는데, 해당 변수를 없애줌.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	private static int list[];
	private static int listvalue[];
	private static int n, m;
	private static StringBuilder sb;

	private static void dfs(int cnt) {
		if (cnt == m) {
			for (int i = 0; i < m; i++) {
				sb.append(list[i]).append(" ");
			}
			sb.append("\n");
			return;
		}

		int saveValue=-1;
		for (int i = 1; i <= n; i++) {
			if (saveValue==listvalue[i-1])
				continue;
			list[cnt] = listvalue[i - 1];
			saveValue = listvalue[i - 1];
			dfs(cnt + 1);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		list = new int[9];
		listvalue = new int[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			listvalue[i] = Integer.parseInt(st.nextToken());
		sb = new StringBuilder();
		Arrays.sort(listvalue);

		dfs(0);

		bw.write(sb.toString());

		bw.close();
		br.close();
	}

}

• 코드

정답 코드 : 기존 N과 M (9)의 코드에서 추가하는 부분에 boolean을 하나 추가해서 오름차순만 출력할 수 있게 하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	private static int list[];
	private static int listvalue[];
	private static boolean visit[];
	private static int n, m;
	private static StringBuilder sb;

	private static void dfs(int cnt) {
		if (cnt == m) {
			boolean check = true;
			for (int i = 1; i < m; i++) {
				if(list[i-1]>list[i])
					check = false;
			}
			if(check) {
				for (int i = 0; i < m; i++) {
					sb.append(list[i]).append(" ");
				}
				sb.append("\n");
			}
			return;
		}

		int saveValue=-1;
		for (int i = 1; i <= n; i++) {
			if (visit[i] || saveValue==listvalue[i-1])
				continue;
			visit[i] = true;
			list[cnt] = listvalue[i - 1];
			saveValue = listvalue[i - 1];
			dfs(cnt + 1);
			visit[i] = false;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		list = new int[9];
		visit = new boolean[9];
		listvalue = new int[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			listvalue[i] = Integer.parseInt(st.nextToken());
		sb = new StringBuilder();
		Arrays.sort(listvalue);

		dfs(0);

		bw.write(sb.toString());

		bw.close();
		br.close();
	}

}

• 코드

정답 코드 : 중복된 값이 출력이 안되기 때문에, 이전 N과 M (6)코드에서 오름차순만 출력되게 하는 부분을 지우고 이전 값을 저장해놨다가 중복되면 출력이 안되도록 하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	private static int list[];
	private static int listvalue[];
	private static boolean visit[];
	private static int n, m;
	private static StringBuilder sb;

	private static void dfs(int cnt) {
		if (cnt == m) {
			for (int i = 0; i < m; i++) {
				sb.append(list[i]).append(" ");
			}
			sb.append("\n");
			return;
		}

		int saveValue=-1;
		for (int i = 1; i <= n; i++) {
			if (visit[i] || saveValue==listvalue[i-1])
				continue;
			visit[i] = true;
			list[cnt] = listvalue[i - 1];
			saveValue = listvalue[i - 1];
			dfs(cnt + 1);
			visit[i] = false;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		list = new int[9];
		visit = new boolean[9];
		listvalue = new int[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			listvalue[i] = Integer.parseInt(st.nextToken());
		sb = new StringBuilder();
		Arrays.sort(listvalue);

		dfs(0);

		bw.write(sb.toString());

		bw.close();
		br.close();
	}

}