Pearlii-Log

문제 풀이 날짜: 2023.05.23
포스트 작성일: 2023.05.25

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 1874번: 스택 수열 (실버2) (문제 링크)

키워드

스택

풀이 접근법

• 1부터 n까지의 수를 탐색하며 적절한 타이밍에 push & pop 해주는 문제이다.
  • 현재 탐색하는 수가 target이라고 할때, 1부터 target까지 스택에 push된 적 없다면 push한다.
    • target이 j보다 크면(>) 스택에 수를 넣을 건데, j가 1부터 시작하는 데다가 target까지 1이라면 스택에 수를 넣을 수 없게 됨. 따라서 등호를 추가해야 한다.
  • 1부터 target 이상의 수가 이미 스택에 push된 적이 있는데, 그것보다 작은 수를 push해야 한다면 이것은 스택으로 구현될 수 없는 순서이다.
  • target과 스택 최상단(stack.peek())의 수가 동일하다면 스택에서 꺼낸다. (pop)
• 연달아 pop했을 때, 이 수들을 늘어놓으면 반드시 내림차순이다.
  • 예: 1, 2, 3, 4를 push하고 pop을 두 번 하면 내림차순 4, 3을 얻는다.
• 내림차순이 성립하지 않으면 다른 수를 push한 다음에 pop한 것이다.
  • 예: 4, 3, 6, 8, 7이 있을 때, 4, 3까지 pop을 하고 6을 push한다.
  • 6을 pop하고 7, 8을 push한다.
  • 그 다음에는 8, 7을 pop한다.

코드

import java.io.*;
import java.util.*;

public class Main {

	private static Stack<Integer> stack = new Stack<>();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] targets = new int[N];
		
		for(int i = 0; i < N; i++) {
			targets[i] = Integer.parseInt(br.readLine());
		}
		
		StringBuilder sb = new StringBuilder();
		
		boolean isValid = true;
		
		int i = 0;
		int j = 1;
		while(i < targets.length || j <= N) {
			int target = targets[i];
			
			//반복문이 시작되자마자 push를 하기 때문에 isEmpty()를 고려하지 않아도 됨.
			if(target >= j) {
				while(j <= target) {
					stack.push(j);
					sb.append("+").append('\n');
					j++;
				}
			}
			else if(Objects.equals(stack.peek(), target)) {
				stack.pop();
				sb.append("-").append('\n');
				i++;
			}
			else {
				isValid = false;
				break;
			}
		}
		
		if(isValid) {
			System.out.print(sb);
		}
		else {
			System.out.print("NO");
		}
	}
}

실버 등급이지만 조건 구현이 조금 까다롭게 느껴지는 문제였다. 처음에는 target >= j의 등호를 빼먹어서 틀리기도 했다. 특히 주의해야 할 점이 있었는데, stack에서 뽑은 수는 primitive type인 int가 아니라 Integer 타입이기 때문에 비교할 때는 equals()를 사용하는 게 더 정확하다. 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week9/day2/Q1874.java

문제 풀이 날짜: 2023.05.23
포스트 작성일: 2023.05.24

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 4949번: 균형잡힌 세상 (실버4) (문제 링크)

키워드

스택

풀이 접근법

• 괄호는 스택으로 짝을 지으면 된다.
• 괄호가 하나도 존재하지 않는 문자도 균형 잡힌 문자이다.
• 괄호의 짝이 맞지 않은 것을 하나라도 발견한다면 즉시 탐색을 멈춘다. (반복문 탈출)
• 그렇다면 스택으로 괄호의 짝을 어떻게 맞출까?
  • 왼쪽 괄호를 만나면 스택에 넣는다.
  • 오른쪽 괄호를 만나면 스택에서 괄호를 하나 poll()하고 그것이 왼쪽 괄호와 짝이 맞는지 확인한다.
  • 스택의 가장 마지막에 넣었던 것이 스택 최상단에 위치하므로, 이렇게 대칭 여부를 판단할 수 있다.
• 주의: 입력으로 괄호의 개수가 부족한 케이스도 준다.
  • 탐색을 모두 마쳤는데 스택에 남은 괄호가 있다면 입력된 괄호의 개수가 부족한 것이다. 이 경우를 처리해주어야 한다. 매 반복이 끝날 때마다 스택도 잘 비워준다.

코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		ArrayList<String> sentences = new ArrayList<>();
		
		while(true) {
			String line = br.readLine();
			
			if(line.equals(".")) {
				break;
			}
			
			sentences.add(line);
		}
		
		Stack<Character> stack = new Stack<>();
		StringBuilder sb = new StringBuilder();
		
		boolean balanced = true;
		for(String sentence : sentences) {
			int length = sentence.length();
			
			for(int i = 0; i < length; i++) {
				char c = sentence.charAt(i);
				
				if(c == '(' || c == '[') {
					stack.push(c);
				}
				
				if(c == ')' || c == ']') {
					if(stack.size() <= 0) {
						balanced = false;
						break;
					}
					
					char bracket = stack.pop();
					
					if(!matches(c, bracket)) {
						balanced = false;
						break;
					}
				}
			}
			
			if (stack.size() > 0) {
				sb.append("no").append('\n');
			}
			else if(balanced == true) {
				sb.append("yes").append('\n');
			}
			else if(balanced == false) {
				sb.append("no").append('\n');
			}
			
			balanced = true;
			stack.clear();
		}
		
		System.out.print(sb);
	}

	private static boolean matches(char c, char bracket) {
		if(bracket == '(' && c == ')'
			|| bracket == '[' && c == ']') {
			return true;
		}
		
		return false;
	}

}

스택의 응용문제 중에서 가장 간단한 유형 중 하나이다. 이 외에도 어떤 문제에서는 물건의 구매와 판매, 돈의 입출금 등의 동작을 0, 1로 구분하여 짝지어야 하는 경우도 생긴다. 그러한 경우에도 스택을 잘 이용해주어야 한다.

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week9/day2/Q4949.java

문제 풀이 날짜: 2023.05.13
포스트 작성일: 2023.05.23

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 2565번: 전깃줄 (골드5) (문제 링크)

키워드

동적 계획법(DP), Comparator

풀이 접근법

• 전깃줄의 교차 여부는 전깃줄이 연결되어 있는 지점의 번호로 식별할 수 있다.
  • 전깃줄 ⓐ가 4-1 로 연결되어 있는데, 전깃줄 ⓑ는 2-2 로 연결되어 있다면 교차하는 것이다.
  • (전깃줄 ⓑ의 연결 번호 - 전깃줄 ⓐ의 연결 번호) 를 왼쪽 & 오른쪽별로 구했을 때 왼쪽 & 오른쪽 중 한 곳이라도 음수라면(0은 나올 수 없음) 두 전깃줄이 교차된 것이다.
• 문제에서는 설치된 전깃줄 N개의 정보를 준다. 그렇다면 전봇대에 아무 것도 설치되지 않은 상태에서 이 전깃줄 N개 중 몇 개를 교차되지 않게 설치할 수 있을지를 찾아야 한다.
  • DP 배열에 교차되지 않게 몇 개까지 설치할 수 있을지를 담는다.
  • 이렇게 (전체 N개 - 설치 가능한 개수)를 계산하면 그 결과가 철거해야 할 개수가 된다.
• 교차되지 않게 설치하는 방법은 위에 적어두었던 ‘번호의 차’를 이용하면 된다. 번호의 차라고 해봤자 이 번호들이 정렬된 상태(Comparator 구현 필요)에서 A와 B가 동시에 오름차순으로 증가하는지만(LIS) 체크하면 교차 여부를 알 수 있다.
  • 쉽게 말해서, A와 B 배열을 가지고 동시에 LIS를 찾으면 된다.

코드

import java.io.*;
import java.util.*;

public class Q2565 {

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

		int N = Integer.parseInt(br.readLine());
		
		LinkedList<int[]> poles = new LinkedList<>();
		
		for(int i = 0; i < N; i++) {
			String[] temp = br.readLine().split(" ");
			
			int A = Integer.parseInt(temp[0]);
			int B = Integer.parseInt(temp[1]);
			
			int[] result = {A, B};
			poles.add(result);
		}
		
		Collections.sort(poles, (o1, o2) -> Integer.compare(o1[0], o2[0]));
		
		int max = Integer.MIN_VALUE;
		int[] DP = new int[N];
		Arrays.fill(DP, 1);
		
		for(int i = 1; i < N; i++) {
			int[] now = poles.get(i);
			
			for(int j = 0; j < i; j++) {
				int[] prev = poles.get(j);
				if(prev[0] < now[0] && prev[1] < now[1]) {
					DP[i] = Math.max(DP[j] + 1, DP[i]);
				}
			}
			max = Math.max(DP[i], max);
		}
		
		System.out.print(N - max);
	}

}

처음에는 철거해야 할 전깃줄을 찾다가 점화식도 세우지 못하고 갈피를 잡지 못하였다. 전깃줄을 하나씩 제거하면서 (100) 남은 전깃줄(500 * 500) 중에서 교차하는 것을 찾으면(500) 시간초과이기 때문이다. 30분정도 고민하다가, 다른 분들의 풀이를 참고하여 내 방식대로 코드를 작성해보았다.

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week8/day1/Q2565.java

참고한 블로그 링크

https://st-lab.tistory.com/138

문제 풀이 날짜: 2023.05.22
포스트 작성일: 2023.05.23

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 1541번: 잃어버린 괄호 (실버2) (문제 링크)

키워드

그리디

풀이 접근법

• 식에 괄호를 여러 개 칠 수 있고, 하나의 괄호 안에 여러 개의 수가 들어갈 수 있다.
• (양수 + 어떤 수) 조합은 괄호를 쳐도 별 일이 일어나지 않는다.
• (음수 + 어떤 수) 조합에 괄호를 칠 때 주의가 필요하다.
  • 괄호 안의 수는 모두 부호가 반대가 된다.
  • 따라서 현재 가리키는 수가 양수라면 그냥 결과에 더해주고, 음수라면 적절한 연산을 한다.
  1. 괄호를 쳐야 하는 경우 : 뒤에 이어지는 수도 양수일 때
  2. 괄호를 치지 않아야 하는 경우 : 뒤에 이어지는 수가 음수일 때 (결괏값이 더 커진다)
• 반복문을 돌다가 음수를 만났다면… 
  • 음수를 만났을 때, 다음 수로 또 음수가 나올 때까지 양수들과 함께 괄호를 친다.
  • 즉, 다음에 나오는 양수들은 무조건 부호를 뒤집어서 더해준다.
• 입력 String의 첫 번째 수부터 음수일 수도 있으니 처리에 주의하자.

코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String formula = br.readLine();
		
		ArrayList<Integer> numbers = new ArrayList<>();
		ArrayList<Character> operators = new ArrayList<>();
		
		StringTokenizer st = new StringTokenizer(formula, "+-");
		while(st.hasMoreTokens()) {
			numbers.add(Integer.parseInt(st.nextToken()));
		}
		
		for(int i = 0; i < formula.length(); i++) {
			char c = formula.charAt(i);
			if(c == '+' || c == '-') {
				operators.add(c);
			}
		}
		
		int result = 0;
		int numIdx = 0;
		int opeIdx = 0;

		//첫 번째로 더하는 수가 양수라면
		if(numbers.size() != operators.size()) {
			result += numbers.get(0);
			numIdx = 1; //처리해주고 인덱스를 하나 증가시킨다.
		}

		int multiplier = 1;
		while(numIdx < numbers.size() || opeIdx < operators.size()) {			
			if(operators.get(opeIdx) == '-') { //음수를 만났다면
				multiplier = -1; //이 뒤로 괄호를 쳐서 음수로 만든다.
			}
			
			result += (numbers.get(numIdx) * multiplier);
			
			numIdx++;
			opeIdx++;
		}
		
		System.out.print(result);
	}

}

괄호의 특성을 이용하면 어렵지 않게 풀 수 있는 그리디 문제이다. 만약 정말로 문자열 사이사이에 괄호를 치려고 하면 조금 위험해진다. (과거의 나라면 그렇게 풀었을 듯하다.) 적당한 덧셈 뺄셈으로만 해결이 가능하다.

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week9/day1/Q1541.java

문제 풀이 날짜: 2023.05.03
포스트 작성일: 2023.05.21

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

프로그래머스 코딩테스트 고득점Kit 힙 편 : 이중우선순위큐 (Lv.3) (문제 링크)

키워드

우선순위 큐, Comparator

풀이 접근법

• 최대로 정렬하는 PriorityQueue와, 최소로 정렬하는 PriorityQueue를 정의한다.
• Comparator를 이용해서 정렬 기준을 아래와 같이 새로 정해주어야 한다.

//방법 1
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
//Collections에도 reverseOrder()가 존재한다.

//방법 2
PriorityQueue<Integer> pq = new PriorityQueue<>(
				(o1, o2) -> Integer.compare(o2, o1)); //o1, o2의 순서가 반대임에 주의

코드

import java.util.*;

public class DualPriorityQueue {
	public int[] solution(String[] operations) {
        int[] answer = new int[2];
        
        PriorityQueue<Integer> minPq = new PriorityQueue<>();
        PriorityQueue<Integer> maxPq = new PriorityQueue<>(
            Comparator.reverseOrder());
        
        for(String operation : operations) {
            String[] temp = operation.split(" ");
            
            String operator = temp[0];
            int operand = Integer.parseInt(temp[1]);
            
            if(operator.equals("I")) {
                minPq.add(operand);
                maxPq.add(operand);
            }
            else if(operator.equals("D")) {
                if(minPq.isEmpty()) {
                    continue;
                }
                
                if(operand > 0) { //최댓값 삭제
                    int key = maxPq.poll();
                    minPq.remove(key);
                }
                else { //최솟값 삭제
                    int key = minPq.poll();
                    maxPq.remove(key);
                }
            }
        }
        
        if(minPq.isEmpty()) {
            return answer;
        }
        
        answer[0] = maxPq.poll();
        answer[1] = minPq.poll();
        
        return answer;
    }
}

정렬 기준이 다른 두 힙을 구현하기만 하면 쉽게 풀 수 있는 문제이다. Comparator를 이용한 Collection의 정렬은 알아두면 여러곳에 응용할 일이 많으니 확실히 익혀두는 것이 좋겠다.

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week7/day1/DualPriorityQueue.java

문제 풀이 날짜: 2023.05.20
포스트 작성일: 2023.05.21

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

Software Expert Academy 1244번: 최대상금 (D3) (문제 링크)

키워드

완전탐색(백트랙킹)

풀이 접근법

• 각 교환 횟수마다의 최댓값을 기록한다고 해도 그것이 마지막까지 최적해임을 보장할 수는 없다. 따라서 완전탐색으로 풀이하였다.
  • 최대 자릿수가 6이고 최대 교환 횟수가 10회이므로 백트랙킹으로 풀어도 시간초과가 되지 않는다.
• 여기서 주의해야 할 점은, 배열 요소의 수는 최대 6개인데 수를 10회 교체하라고 하면, 이미 바꿨던(swap) 부분을 또 다시 바꿔야 한다. 따라서 6번째 값을 가리킬 때는 다시 현재 인덱스(lastIndex)를 0으로 되돌려서 탐색한다.
• 입력 패널이 “00000”일 때나 패널의 교환 결과가 "09"여서 0을 제거해야 하는 경우 등을 주의해야 한다.

코드

import java.io.*;

public class SWEA1244 {

	private static final int MAX_LENGTH = 6;
	private static int answer = -1;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= T; test_case++) {
			String temp[] = br.readLine().split(" ");
			
			char[] prize = temp[0].toCharArray();
			int count = Integer.parseInt(temp[1]);
		
			DFS(prize, count, 0, 0);
			
			if(answer == -1) { //교환할 수 없는 상황이라면
				answer = Integer.parseInt(temp[0]);
			}
			
			sb.append("#" + test_case + " ").append(answer).append('\n');
		}
		
		System.out.print(sb);
	}
	
	public static void DFS(char[] prize, int count, int depth, int lastIndex) {
				
		if(depth == count) {
			String result = String.valueOf(prize);
			
			answer = Math.max(Integer.parseInt(result), answer);
			
			return;
		}
		
		if(lastIndex % (MAX_LENGTH - 1) == 0) {
			lastIndex = 0;
		}
		
		for(int i = lastIndex; i < prize.length - 1; i++) {
			for(int j = i + 1; j < prize.length; j++) {
				//i번째 수와 j번째 수를 swap
				char temp = prize[i];
				prize[i] = prize[j];
				prize[j] = temp;
				
				//dfs 호출
				DFS(prize, count, depth + 1, lastIndex + 1);
				
				//원복
				temp = prize[i];
				prize[i] = prize[j];
				prize[j] = temp;
			}
		}
		
		return;
	}

}

어렵지 않은 백트랙킹 응용 문제라고 생각한다. 다만 여기서 재귀의 depth가 지정된 count까지 도달하지 못하는 경우(answer == -1) 가장 처음의 입력값을 가지도록 해주었다. count까지 도달하지 못하는 이유로는 여러 가지가 있지만 정확한 해결방안을 알아내지 못해 모호하게 예외처리를 하게 되었는데, 차후 복습하며 코드를 정확하게 개선해야겠다.

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week8/day7/SWEA1244.java

문제 풀이 날짜: 2023.05.19
포스트 작성일: 2023.05.19

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

Software Expert Academy 1249번 : 보급로 (D4) (문제 링크)

키워드

동적 계획법(DP), BFS

풀이 접근법

• 일반적인 BFS와는 다르게 갔던 장소(visited[r][c] = true)를 다시 갈 수 있어야 한다. 또, 새롭게 발견한 경로의 최소 비용으로 갱신하는 부분이 필요하다.
• 따라서 최소비용은 DP 배열에 갱신하고, DP값이 갱신된 노드는 다시 Queue에 추가하여 탐색을 계속한다.
• 즉, 어떤 점 (r, c)는 왼쪽(r, c - 1)과 위쪽(r - 1, c)에서 방문할 수 있다. 여기서 이미 왼쪽 점으로부터 방문하여 queue에 현재의 점(r, c)이 추가되었다고 해보자.
  • 그런데 이 점은 위쪽에서부터 방문한 값이 최소인 상황이다. 이런 상황에서 위쪽으로부터 온 DP값으로 비용이 갱신되었다면 다시 BFS 탐색을 해주어야 이 점 (r, c)와 이어진 다른 점들까지 연쇄적으로 최솟값을 갱신할 수가 있다.
  • 그렇지 않으면 해당 점까지의 최솟값은 갱신될 수 있어도, 이후로 이어진 경로들까지 이 최신 정보가 반영되지 않는다.
  • 결국 방문할 점을 Queue에 추가하는 조건이 1.visited 여부 2.새 값 갱신 여부 이렇게 총 2가지인 것.

코드

import java.io.*;
import java.util.*;

public class SWEA1249 {
	
	private static int N;
	private static int[] dx = {1, 0, -1, 0};
	private static int[] dy = {0, 1, 0, -1};
	
	private static int[][] matrix;
	private static int[][] DP;
	private static boolean[][] visited;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(br.readLine());
			
			matrix = new int[N][N];
			DP = new int[N][N];
			visited = new boolean[N][N];
			
			for(int i = 0; i < N; i++) {
				char[] lines = br.readLine().toCharArray();
				for(int j = 0; j < N; j++) {
					matrix[i][j] = lines[j] - '0';
					DP[i][j] = Integer.MAX_VALUE;
				}
			}
			
			BFS(0, 0);
			
			sb.append("#" + test_case + " ").append(DP[N - 1][N - 1]).append('\n');
		}

		System.out.print(sb);
	}
	
	public static void BFS(int startR, int startC) {
		Queue<Node> queue = new LinkedList<>();
		queue.add(new Node(startR, startC));
		DP[startR][startC] = 0;
		visited[startR][startC] = true;
		
		while(!queue.isEmpty()) {
			Node n = queue.poll();
			
			int nr = 0;
			int nc = 0;
			for(int i = 0; i < dx.length; i++) {
				nr = n.row + dy[i];
				nc = n.col + dx[i];
				
				if(isValid(nr, nc)) {
					//이미 방문한 적 있더라도 더 작은 DP값이 발견되면 다시 방문
					if(!visited[nr][nc] || DP[n.row][n.col] + matrix[nr][nc] < DP[nr][nc]) {
						DP[nr][nc] = DP[n.row][n.col] + matrix[nr][nc];
						visited[nr][nc] = true;
						queue.add(new Node(nr, nc));	
					}
				}
			}
		}
		
		return;
	}
	
	public static boolean isValid(int row, int col) {
		return (row >= 0 && col >= 0 && row < N && col < N);
	}

}

class Node{
	int row;
	int col;
	
	public Node(int row, int col) {
		this.row = row;
		this.col = col;
	}
}

BFS와 DP가 결합된 형태는 처음 풀어보았다. 문제의 댓글을 보니 다익스트라로 접근할 수도 있다고 한다. 여기서는 DP가 갱신되는 시점을 정하는 것과 방문한 점을 또 다시 방문할 수 있도록 조건을 적절히 수정해주는 것이 매우 중요했다.

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week8/day5/SWEA1249.java

문제 풀이 날짜: 2023.05.12
포스트 작성일: 2023.05.18

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

문제 출처

백준 온라인 저지 11054번: 가장 긴 바이토닉 부분 수열 (골드4) (문제 링크)

키워드

동적 계획법(DP)

풀이 접근법

• 가장 긴 증가하는 부분 수열(LIS)의 응용 문제이다. (백준 온라인 저지 11053번 문제 링크)
• 이전에 LIS를 풀어본 적이 있어서 비교적 접근이 쉬웠다. LIS는 현재 가리키는 수(arr[i])를 기준으로 그 이전에 존재하는 수들과 (arr[j], j = 0 ~ i-1) 비교하면서, 이전의 수(arr[j])보다 현재 가리키는 수(arr[i])가 더 크다면 이것을 증가하는 부분 수열에 합치고 현재까지의 최대 길이를 갱신하는(DP[j] + 1) 문제였다.
• 그런데 바이토닉 부분 수열은 증가하다가 감소하는 터닝포인트가 있는 수열이다. 
• 반드시 수의 크기가 증가하다가 감소하는 터닝포인트가 존재하며, 그 부분을 기점으로 앞으로는 더 큰 값을 수열에 포함시킬지 더 작은 값을 포함시킬지를 결정한다. 길이보다도 대소비교의 전환을 핵심으로 두고 풀었다.
  • DP 배열을 2차원으로 선언해서 증가할 때의 길이[0], 감소할 때의 길이[1]를 각각 기록한다.
  • LIS 문제와 같은 형태로 이중 for문을 이용해 수를 탐색한다. 현재 i가 가리키는 수를 기점으로 그 이전의 값들을 탐색한다.
  • 앞 부분은 그냥 LIS와 같이 증가하는 수열을 찾으며 길이를 기록하는데, 다음에 탐색할 수가 현재의 수보다 작으면서도  DP[j][0] > DP[j][1] 인 시점이 나타나면 그곳이 터닝포인트다.
  • 즉, 해당 숫자까지 증가하는 수열의 길이(DP[j][0])가 감소하는 수열의 길이(DP[j][1])보다 훨씬 길 때를 ‘증가하다가 감소하는 포인트’로 삼는다.

코드

import java.io.*;
import java.util.StringTokenizer;

public class Q11054 {

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

		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int[][] DP = new int[N][2];
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			DP[i][0] = 1; //증가하는 구간에서의 길이
			DP[i][1] = 0; //감소하는 구간에서의 길이
		}
		
		for(int i = 1; i < N; i++) {
			int target = arr[i];
			for(int j = 0; j < i; j++) {
				if(arr[j] < target) { //증가
					DP[i][0] = Math.max(DP[j][0] + 1, DP[i][0]);
				}
				else if(arr[j] > target) { //감소
					if(DP[j][0] > DP[j][1]) { //증가하다가 감소하는 포인트라면
						DP[i][1] = Math.max(DP[j][0] + 1, DP[i][1]);
					}
					else {
						DP[i][1] = Math.max(DP[j][1] + 1, DP[i][1]);
					}
				}
			}
		}
		
		int result = -1;
		for(int i = 0; i < N; i++) {
			int max = Math.max(DP[i][0], DP[i][1]);
			if(max > result) {
				result = max;
			}
		}
		
		System.out.print(result);
	}

}

이전에 LIS를 풀 때는 많이 틀리기도 했고, 도저히 풀리지 않아서 다른 사람의 풀이법을 참고해서 코드를 작성했었다. 하지만 한 번 풀이방식에 익숙해지고 나니 LIS처럼 푸는 사고방식이 머리에 정착되었고, 응용문제는 비교적 쉽게 풀 수 있었다. DP 문제는 DP식 사고방식을 내것으로 만드는 게 정말 중요한 것 같다. 이 외에도 다양한 DP 응용 문제들이 있으니 꼭 한 번은 풀어보아야겠다.

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week7/day7/Q11054.java