링크 →

11054번: 가장 긴 바이토닉 부분 수열

• 아영

  • 코드
  • 시간,메모리

• 성우

  • 코드
  • 시간,메모리

• 은영

  • 코드
  • 시간,메모리

• 건

  • 코드

  package day_0326;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.StringTokenizer;
  
  public class BOJ11054 {
  
  	public static void main(String[] args) throws IOException{
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer stk;
  		
  		int n = Integer.parseInt(br.readLine());
  		
  		int[] list = new int[n];
  		
  		stk = new StringTokenizer(br.readLine());
  		for (int i = 0; i < n; i++) {
  			list[i] = Integer.parseInt(stk.nextToken());
  		}
  		
  		int[] dp = new int[n];
  		for (int i = 0; i < n; i++) {
  			dp[i] = 1;
  			
  			for (int j = 0; j < i; j++) {
  				if (list[j] < list[i] && dp[i] < dp[j] + 1) {
  					dp[i] = dp[j] + 1;
  				}
  			}
  		}
  		
  		int[] dp2 = new int[n];
  		for (int i = n - 1; i >= 0; i--) {
  			dp2[i] = 1;
  			
  			for (int j = n - 1; j > i; j--) {
  				if (list[j] < list[i] && dp2[i] < dp2[j] + 1) {
  					dp2[i] = dp2[j] + 1;
  				}
  			}
  		}
  		
  		int answer = 0;
  		for (int i = 0; i < n; i++) {
  			if (dp[i] + dp2[i] > answer) {
  				answer = dp[i] + dp2[i];
  			}
  		}
  		
  		System.out.println(answer - 1);
  	}
  
  }
  

  • 시간,메모리

  

• 용문

  • 코드

  class BJ11054 {
      
      private var N: Int = 0
      private var nums: [Int] = []
      private var up: [Int] = []
      private var down: [Int] = []
      
      public func solve() {
          readComponents()
          calcUp()
          calcDown()
          printAnswer()
      }
      
      private func readComponents() {
          N = Int( readLine()! )!
          nums = readLine()!.split(separator: " ").map{ Int($0)! }
          
          up = .init(repeating: 1, count: N)
          down = .init(repeating: 1, count: N)
      }
      
      private func calcUp() {
          for index in 0..<N {
              for sindex in 0..<index {
                  if nums[sindex] < nums[index], up[index] < up[sindex] + 1 {
                      up[index] += 1
                  }
              }
          }
      }
      
      private func calcDown() {
          for index in stride(from: N - 1, through: 0, by: -1) {
              for sindex in stride(from: N - 1, to: index, by: -1) {
                  if nums[sindex] < nums[index], down[index] < down[sindex] + 1 {
                      down[index] += 1
                  }
              }
          }
      }
      
      private func printAnswer() {
          var result = -1
          
          for index in 0..<N {
              result = max(result, up[index] + down[index])
          }
          print(result - 1)
      }
  }
  
  BJ11054().solve()