'분류 전체보기' 카테고리의 글 목록 (48 Page)

분류 전체보기

[JAVA] 백준 2437번 : 저울 2020.10.16
[JAVA] 백준 : 1759번 : 암호 만들기 2020.10.14
[JAVA] 백준 16916번 : 부분 문자열 2020.10.13
[JAVA] 백준 16172번 : 나는 친구가 적다 (Large) 2020.10.13
[JAVA] 백준 1701번 : Cubeditor 2020.10.12
[JAVA] 백준 11054번 : 가장 긴 바이토닉 부분 수열 2020.10.11
[JAVA] 백준 1013번 : Contact 2020.10.09
[JAVA] 백준 11048번 : 이동하기 2020.10.09

[JAVA] 백준 2437번 : 저울

2020. 10. 16. 16:54

코드

정답 코드 : 그리디 알고리즘 문제이다. 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);
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 11049번 : 행렬 곱셈 순서 (0)	2020.10.22
[JAVA] 백준 5639번 : 이진 검색 트리 (0)	2020.10.21
[JAVA] 백준 : 1759번 : 암호 만들기 (0)	2020.10.14
[JAVA] 백준 16916번 : 부분 문자열 (0)	2020.10.13
[JAVA] 백준 16172번 : 나는 친구가 적다 (Large) (0)	2020.10.13

[JAVA] 백준 : 1759번 : 암호 만들기

2020. 10. 14. 23:10

코드

정답 코드 : 처음 사전순으로 정렬 한다음 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;
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 5639번 : 이진 검색 트리 (0)	2020.10.21
[JAVA] 백준 2437번 : 저울 (0)	2020.10.16
[JAVA] 백준 16916번 : 부분 문자열 (0)	2020.10.13
[JAVA] 백준 16172번 : 나는 친구가 적다 (Large) (0)	2020.10.13
[JAVA] 백준 1701번 : Cubeditor (0)	2020.10.12

[JAVA] 백준 16916번 : 부분 문자열

2020. 10. 13. 22:37

코드

실패 코드1 : contains를 통해 포함이 되는지 안되는지 판별 후 포함되면 1, 포함되지않으면 0 출력 => 시간초과

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

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 firstInput = br.readLine();
		String secondInput = br.readLine();
		
		if(firstInput.contains(secondInput))
			System.out.println(1);
		else
			System.out.println(0);
    }
}

실패 코드2 : firstInput 배열에서 secondInput의 length index만큼부터 시작해서 같으면 그전이 다맞나 체크함. => 시간초과

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

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 a = br.readLine();
		char[] firstInput = a.toCharArray();
		String b = br.readLine();
		char[] secondInput = b.toCharArray();
		
		boolean check = false;
		for(int i=secondInput.length-1;i<firstInput.length;i++) {
			if(check)
				break;
			if(firstInput[i] == secondInput[secondInput.length-1]) {
				int index = secondInput.length-1;
				check = true;
				for(int j = i; j>i-secondInput.length;j--) {
					if(firstInput[j]!=secondInput[index--]) {
						check = false;
						break;
					}
				}
			}
		}
		
		if(check)
			System.out.print(1);
		else
			System.out.print(0);
    }
}

성공 코드 : KMP 알고리즘을 공부한 뒤 KMP 알고리즘으로 풀어보았다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {	
	static String firstString, secondString;
	static int pi[];
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		firstString = br.readLine();
		secondString = br.readLine();
		pi = new int[secondString.length()];
				
		System.out.println(KMP());
	}

	// KMP 알고리즘 - pi[] 배열에서 주어진 문자열의 인덱스 0부터 i까지의 부분 문자열 중
	// 접두사 == 접미사가 되는 가장 긴 접두사의 길이를 넣는다.
	// 현재 밑 코드에서 접두사는 j(왼쪽), 접미사는 i(오른쪽)이다.
	static int KMP() {
		// j 접두사
		int j = 0;
		
		// i 접미사
	    for (int i = 1; i < secondString.length(); ++i) {
	        while (j > 0 && secondString.charAt(i) != secondString.charAt(j)) j = pi[j - 1];
	        if (secondString.charAt(i) == secondString.charAt(j)) pi[i] = ++j;
	    }
	    
	    j = 0;
	    for (int i = 0; i < firstString.length(); ++i) {
	        while (j > 0 && firstString.charAt(i) != secondString.charAt(j)) j = pi[j - 1];
	        if (firstString.charAt(i) == secondString.charAt(j)) {
	            if (j == secondString.length() - 1) {
	                return 1;
	            }
	            else ++j;
	        }
	    }
	    return 0;
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 2437번 : 저울 (0)	2020.10.16
[JAVA] 백준 : 1759번 : 암호 만들기 (0)	2020.10.14
[JAVA] 백준 16172번 : 나는 친구가 적다 (Large) (0)	2020.10.13
[JAVA] 백준 1701번 : Cubeditor (0)	2020.10.12
[JAVA] 백준 11054번 : 가장 긴 바이토닉 부분 수열 (0)	2020.10.11

[JAVA] 백준 16172번 : 나는 친구가 적다 (Large)

2020. 10. 13. 22:30

코드

실패 코드 : KMP를 써보지 않고 숫자를 모두 제외한 뒤 Contains을 통해 확인해본 결과 시간 초과, KMP 알고리즘을 사용해야지 시간 초과가 나지 않는다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {	
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			
		String firstString = br.readLine();
		String secondString = br.readLine();
		
		for(int i = 0; i < firstString.length(); i++) {
			if(firstString.charAt(i) >= '0' && firstString.charAt(i) <= '9') {
				firstString = firstString.substring(0, i) + firstString.substring(i--+1);
			}
		}
		
		for(int i = 0; i < secondString.length(); i++) {
			if(secondString.charAt(i) >= '0' && secondString.charAt(i) <= '9') {
				secondString = secondString.substring(0, i) + secondString.substring(i--+1);
			}
		}
		
		if(firstString.contains(secondString))
			System.out.println("1");
		else
			System.out.println("0");
	}
}

실패 코드 : KMP 알고리즘을 통해서 푼 코드이다. 왜 안되는지 모르겠다.... 계속 메모리 초과가 뜬다...

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Algorithm {	
	static String firstString, secondString;
	static int pi[];
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		firstString = br.readLine();
		secondString = br.readLine();
		pi = new int[secondString.length()];
		
		for(int i = 0; i < firstString.length(); i++) {
			if(firstString.charAt(i) >= '0' && firstString.charAt(i) <= '9') {
				firstString = firstString.substring(0, i) + firstString.substring(i--+1);
			}
		}
		
		System.out.println(KMP());
	}

	// KMP 알고리즘 - pi[] 배열에서 주어진 문자열의 인덱스 0부터 i까지의 부분 문자열 중
	// 접두사 == 접미사가 되는 가장 긴 접두사의 길이를 넣는다.
	// 현재 밑 코드에서 접두사는 j(왼쪽), 접미사는 i(오른쪽)이다.
	static int KMP() {
		// j 접두사
		int j = 0;
		
		// i 접미사
	    for (int i = 1; i < secondString.length(); ++i) {
	        while (j > 0 && secondString.charAt(i) != secondString.charAt(j)) j = pi[j - 1];
	        if (secondString.charAt(i) == secondString.charAt(j)) pi[i] = ++j;
	    }
	    
	    j = 0;
	    for (int i = 0; i < firstString.length(); ++i) {
	        while (j > 0 && firstString.charAt(i) != secondString.charAt(j)) j = pi[j - 1];
	        if (firstString.charAt(i) == secondString.charAt(j)) {
	            if (j == secondString.length() - 1) {
	                return 1;
	            }
	            else ++j;
	        }
	    }
	    return 0;
	}
}

정답 코드 : KMP 알고리즘을 통해서 푼 코드이다. 앞 선 코드에선 subString으로 숫자를 없애 주는 부분을 KMP 알고리즘에서 숫자를 continue만 해주니까 통과했다..

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {	
	static String firstString, secondString;
	static int pi[];
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		firstString = br.readLine();
		secondString = br.readLine();
		pi = new int[secondString.length()];
		
		System.out.println(KMP());
	}

	// KMP 알고리즘 - pi[] 배열에서 주어진 문자열의 인덱스 0부터 i까지의 부분 문자열 중
	// 접두사 == 접미사가 되는 가장 긴 접두사의 길이를 넣는다.
	// 현재 밑 코드에서 접두사는 j(왼쪽), 접미사는 i(오른쪽)이다.
	static int KMP() {
		// j 접두사
		int j = 0;
		
		// i 접미사
	    for (int i = 1; i < secondString.length(); ++i) {
	        while (j > 0 && secondString.charAt(i) != secondString.charAt(j)) j = pi[j - 1];
	        if (secondString.charAt(i) == secondString.charAt(j)) pi[i] = ++j;
	    }
	    
	    j = 0;
	    for (int i = 0; i < firstString.length(); ++i) {
            if(firstString.charAt(i)>='0' && firstString.charAt(i)<='9') continue; // 숫자를 만나면 다음 문자로
	        while (j > 0 && firstString.charAt(i) != secondString.charAt(j)) j = pi[j - 1];
	        if (firstString.charAt(i) == secondString.charAt(j)) {
	            if (j == secondString.length() - 1) {
	                return 1;
	            }
	            else ++j;
	        }
	    }
	    return 0;
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 : 1759번 : 암호 만들기 (0)	2020.10.14
[JAVA] 백준 16916번 : 부분 문자열 (0)	2020.10.13
[JAVA] 백준 1701번 : Cubeditor (0)	2020.10.12
[JAVA] 백준 11054번 : 가장 긴 바이토닉 부분 수열 (0)	2020.10.11
[JAVA] 백준 1013번 : Contact (0)	2020.10.09

[JAVA] 백준 1701번 : Cubeditor

2020. 10. 12. 22:28

코드

정답 코드 : KMP 알고리즘을 통해 풀었다. pi 배열을 통해 왼쪽부터 한 글자씩 제거한 문자열을 인자로 넣어 모든 가능한 부분문자열 중에서 접두사와 접미사가 같은 문자열의 최대 길이 를 구하면 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {	
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s = br.readLine();
		int n = s.length(), max = 0;
		
		for(int i = 0; i < n; i++) 
			max = Math.max(max, KMP(s.substring(i, n)));
		
		System.out.println(max);
	}

	// KMP 알고리즘 - pi[] 배열에서 주어진 문자열의 인덱스 0부터 i까지의 부분 문자열 중
	// 접두사 == 접미사가 되는 가장 긴 접두사의 길이를 넣는다.
	// 현재 밑 코드에서 접두사는 j(왼쪽), 접미사는 i(오른쪽)이다.
	static int KMP(String s) {
		// j 접두사
		int j = 0, n = s.length(), max = 0;
		int pi[] = new int[n];
		
		// i 접미사
		for(int i = 1; i < n; i++) {
			while(j > 0 && s.charAt(i) != s.charAt(j)) 
				j = pi[j-1];
			
			if(s.charAt(i) == s.charAt(j)) 
				max = Math.max(max, pi[i] = ++j);
		}
		return max;
	}
}

KMP 알고리즘

1) 기본적인 문자열 탐색 알고리즘은 O(전체 문자열 길이 * 찾으려는 문자열 길이) 만큼 걸리지만, 이 KMP 알고리즘은 O(전체 문자열 길이 + 찾으려는 문자열 길이) 만 걸리는 효율적인 알고리즘이다.

2) 이렇게 시간복잡도를 줄일 수 있는 이유는 바로 문자 하나씩 비교하는 것이 아니라 이전에 이미 비교했던 중간 부분을 건너뛰며 비교하기 때문이다.

3) 찾고자 하는 문자열이 왼쪽부터 시작해서 가질 수 있는 모든 문자열들 중, 접두사와 접미사가 같은 문자열의 최대 길이를 구해서 이를 활용하는 알고리즘.

예를들어, tomato가 있다면

<접두사>

tom

toma

tomat

tomato

이 6개가 banana의 접두사(prefix) 입니다.

<접미사>

ato

mato

omato

tomato

이 6개가 banana의 접미사(suffix) 입니다.

여기서 접두사와 접미사를 를 비교해보면

t, o -> x

to, to -> o

tom, ato -> x

toma, mato -> x

tomat, omato -> x

tomato, tomato -> 자기자신은 당연히 일치하니까 애초에 비교대상에서 제외됨.

이렇게 비교해서 tomato란 문자열에서 접두사와 접미사가 일치하는 최대의 길이는 2가 된다.

<보다 잘 설명되어있는 링크> bowbowbow.tistory.com/6#comment5168448

'algorithm' 카테고리의 다른 글

[JAVA] 백준 16916번 : 부분 문자열 (0)	2020.10.13
[JAVA] 백준 16172번 : 나는 친구가 적다 (Large) (0)	2020.10.13
[JAVA] 백준 11054번 : 가장 긴 바이토닉 부분 수열 (0)	2020.10.11
[JAVA] 백준 1013번 : Contact (0)	2020.10.09
[JAVA] 백준 11048번 : 이동하기 (0)	2020.10.09

[JAVA] 백준 11054번 : 가장 긴 바이토닉 부분 수열

2020. 10. 11. 14:34

코드

정답 코드 : lis / lds 배열에 해당 인덱스부터 마지막 인덱스까지 가장 긴 증가 / 감소하는 부분 수열 값을 넣어주고 합의 최대 값을 출력

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {	
	static int N;
	static int[] inputArray;
	static int[] lis;
	static int[] lds;
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		N = Integer.parseInt(br.readLine());		
		lis = new int[N];	
		lds = new int[N];	
		inputArray = new int[N];		
 
		StringTokenizer st = new StringTokenizer(br.readLine()); 
		for (int i = 0; i < N; i++) 
			inputArray[i] = Integer.parseInt(st.nextToken());	
 
		LIS();
		LDS();
		
		int max = 0;
		for(int i = 0; i < N; i++) {
			if(max < lis[i] + lds[i])  
				max = lis[i] + lds[i];			
		}
 
		System.out.println(max - 1);
	}
 
	
	
	static void LIS() { 
		for(int i = 0; i < N; i++) {
			lis[i] = 1;
			
			for(int j = 0; j < i; j++) {
				if(inputArray[j] < inputArray[i] && lis[i] < lis[j] + 1)
					lis[i] = lis[j] + 1;;
			}
		}
	}
 
 
	
	static void LDS() {		
		for (int i = N - 1; i >= 0; i--) {			
			lds[i] = 1;			
			
			for (int j = N - 1; j > i; j--) {
				if (inputArray[j] < inputArray[i] && lds[i] < lds[j] + 1) 
					lds[i] = lds[j] + 1;	
			}
		}
	
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 16172번 : 나는 친구가 적다 (Large) (0)	2020.10.13
[JAVA] 백준 1701번 : Cubeditor (0)	2020.10.12
[JAVA] 백준 1013번 : Contact (0)	2020.10.09
[JAVA] 백준 11048번 : 이동하기 (0)	2020.10.09
[JAVA] 백준 17070번 : 파이프 옮기기 1 (0)	2020.10.07

[JAVA] 백준 1013번 : Contact

2020. 10. 9. 16:20

코드

정답 코드 : 정규식을 통하여 정규식에 맞으면 StringBuilder에 append시켜준 뒤 반복문을 빠져나와서 출력해주었다.

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));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.valueOf(st.nextToken());
		StringBuilder sb = new StringBuilder();
		String s = "((100+1+)|(01))+";
		
		for(int i = 0; i < N; i++) {
			String temp = br.readLine();
			if(temp.matches(s))
				sb.append("YES");
			else
				sb.append("NO");
			sb.append("\n");
		}

		System.out.print(sb);
	}
}

다른 사람 코드 : maivve.tistory.com/208를 보고 참고하였다. 정규식을 사용하는 것보다 오토마타 전이 그래프(DFA) 를 직접 그려보는 것 + 오토마타 상태 그래프를 바탕으로 알고리즘을 짜서 코딩하는 것이 더 빠르다고 한다. 링크를 통해서 한번 익혀보면 좋을 것 같다.

다른 링크 : eine.tistory.com/entry/%EB%B0%B1%EC%A4%80%EC%A0%80%EC%A7%80-1013%EB%B2%88-Contact-2671%EB%B2%88-%EC%9E%A0%EC%88%98%ED%95%A8-%EC%8B%9D%EB%B3%84-%ED%92%80%EC%9D%B4

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

public class Algorithm {
	static StringBuilder sb;

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

		int n = Integer.valueOf(st.nextToken());
		sb = new StringBuilder();

		while (n-- > 0) {
			String jeonPa = br.readLine();

			int state = 0;
			for (int i = 0; i < jeonPa.length(); i++) {
				char num = jeonPa.charAt(i);
				state = getState(state, num);

				if (state == -1) {
					break;
				}
			}

			if (state == 0 || state == 3 || state == 6 || state == 7) {
				sb.append("YES");
			} else {
				sb.append("NO");
			}

			sb.append("\n");
		}

		System.out.print(sb.toString());
	}

	// 오토마타 상태 그래프에 맞게 출력
	static int getState(int state, char ch) {
		if (ch == '0') {
			switch (state) {
			case 0:
				return 1;
			case 2:
				return 4;
			case 3:
				return 1;
			case 4:
				return 5;
			case 5:
				return 5;
			case 6:
				return 1;
			case 7:
				return 8;
			case 8:
				return 5;
			}
		}

		if (ch == '1') {
			switch (state) {
			case 0:
				return 2;
			case 1:
				return 3;
			case 3:
				return 2;
			case 5:
				return 6;
			case 6:
				return 7;
			case 7:
				return 7;
			case 8:
				return 0;
			}
		}

		return -1;
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1701번 : Cubeditor (0)	2020.10.12
[JAVA] 백준 11054번 : 가장 긴 바이토닉 부분 수열 (0)	2020.10.11
[JAVA] 백준 11048번 : 이동하기 (0)	2020.10.09
[JAVA] 백준 17070번 : 파이프 옮기기 1 (0)	2020.10.07
[JAVA] 백준 11051번 : 이항 계수 2 (0)	2020.10.06

[JAVA] 백준 11048번 : 이동하기

2020. 10. 9. 15:37

코드

실패 코드 : DP 분류에 있는 문제를 눌렀는데 bfs로 풀 수 있는 문제 같아서 bfs로 구현해 보았다. 결과는 시간초과..

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

public class Main {
	static int[] x = { 1, 0, 1 };
	static int[] y = { 0, 1, 1 };
	static int N, M, max = 0;
	static int[][] array;

	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());
		M = Integer.parseInt(st.nextToken());
		array = new int[N][M];

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

		System.out.println(max);
	}

	static void bfs(int a, int b, int count) {
		count += array[a][b];

		if (a == N - 1 && b == M - 1) {
			if (count > max)
				max = count;
			return;
		}

		for (int direction = 0; direction < 3; direction++) {
			int r = a + x[direction];
			int c = b + y[direction];

			if (r >= 0 && c >= 0 && r < N && c < M)
				bfs(r,c,count);
		}
	}

}

설명 : dp문제 답게 dp로 풀었다. 사진에서 보듯이 현재 위치에서 (-1,-1), (-1,0), (0,-1) 한 위치의 값들 중 가장 큰값을 현재 위치의 값과 더 해준다. 이렇게 (N, M)까지 반복문을 돌리면 N, M 위치엔 (0, 0)위치에서 (+1,0), (0,+1), (+1, +1)하면서 더해준 값 중 가장 큰 값이 저장되어 있는다.

정답 코드 : 위에서 쓴 식으로 풀어낸 코드이다.

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));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] array = new int[N+1][M+1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= M; j++)
				array[i][j] = Integer.parseInt(st.nextToken());
		}
		
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) 
				array[i][j] += Math.max(array[i-1][j-1], Math.max(array[i-1][j], array[i][j-1]));
		}
		
		System.out.println(array[N][M]);
	}

}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 11054번 : 가장 긴 바이토닉 부분 수열 (0)	2020.10.11
[JAVA] 백준 1013번 : Contact (0)	2020.10.09
[JAVA] 백준 17070번 : 파이프 옮기기 1 (0)	2020.10.07
[JAVA] 백준 11051번 : 이항 계수 2 (0)	2020.10.06
[JAVA] 백준 1991번 : 트리 순회 (0)	2020.10.05

PREV 1 ···45 46 47 48 49 50 51 ···57 NEXT

선장 일지