Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • 수학
  • 백트래킹
  • 트리
  • 위상 정렬
  • 그래프
  • 분할정복
  • 동적계획법
  • 스택
  • 브루트포스
  • 조합론
  • 우선순위큐
  • 세그먼트 트리
  • 백준
  • 트라이
  • KMP
  • 투포인터
  • 누적합
  • 구현
  • 기하
  • 이분탐색
  • UC++
  • 정렬
  • SCC
  • 최소 스패닝 트리
  • 문자열
  • 큐
  • C++
  • 정수론
  • LCA
  • 유니온 파인드

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite

전자오락 공방

[C++]백준 - 14002번 문제
공부 및 정리/백준 코드

[C++]백준 - 14002번 문제

2021. 9. 22. 16:58

14002번: 가장 긴 증가하는 부분 수열 4 (acmicpc.net)

 

14002번: 가장 긴 증가하는 부분 수열 4

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

 

14002번 : 가장 긴 증가하는 부분 수열 4


수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력


첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

 

출력


첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

 

 


 

생각해 볼 점


기존의 가장 긴 증가하는 수열 문제의 DP 알고리즘을 사용하되,

 

역추적을 담당할 trace라는 배열을 하나 더 지정합니다.

 

trace 배열은 수열의 이전 index를 저장합니다. 만약 수열의 시작점이라면 -1을 저장하고 있습니다.

 

만약 문제에서처럼, {10, 20, 10, 30, 20, 50}이 입력으로 들어왔다면,

 

trace 수열은 {-1, 0, -1, 1, 2, 3}이 됩니다.

 

DP 알고리즘을 모두 마치면, 가장 긴 수열의 길이와 마지막 index를 가져옵니다.

 

예시 입력대로라면, 길이는 4, 마지막 index는 5가 될 것입니다.

 

이제, -1이 나올 때까지 trace[index]를 실행합니다. 실행 도중에 해당 index의 수를 저장합니다.

 

trace[5] = 3  &    {50}

trace[3] = 1  &    {30, 50}

trace[1] = 0  &    {20, 30, 50}

trace[0] = -1  &    {10, 20 , 30, 50}     //종료

 

 

코드


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
	int N;
	scanf("%d", &N);
	
	int *p = new int[N];
	int *dp = new int[N];
	int *trace = new int[N];
	fill_n(trace, N, -1);
	
	int result = 0;
	int for_tracing = 0;	//역추적 시작점
    
    //DP 알고리즘
	for(int i = 0; i < N; i++)
	{
	    scanf("%d", &p[i]);
	    int maxx = 0;
	    dp[i] = 1;
	    for(int j = i - 1; 0 <= j; j--)
	    {
	        if(p[j] < p[i] && maxx < dp[j])
	        {
	            maxx = dp[j];
	            dp[i] = dp[j] + 1;
	            trace[i] = j;
	        }
	    }
        //가장 긴 수열이 갱신되었을 경우
	    if(result < dp[i]) 
	    {
	        result = dp[i];
	        for_tracing = i;
	    }
	}
	
	printf("%d\n", result);
    
    //역추적
	vector<int> v;
	while(true)
	{
	    if(for_tracing == -1) break;
	    v.push_back(p[for_tracing]);
	    for_tracing = trace[for_tracing];
	}
	
	for(int i = result - 1; 0 <= i; i--) printf("%d ", v[i]);
    delete[] p;
	delete[] dp;
	delete[] trace;
	return 0;
}

 

그 외


 

저작자표시 (새창열림)

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++]백준 - 5639번 문제  (0) 2021.09.24
[C++]백준 - 2263번 문제  (0) 2021.09.24
[C++]백준 - 1450번 문제  (0) 2021.09.22
[C++]백준 - 1991번 문제  (0) 2021.09.20
[C++]백준 - 1967번 문제  (0) 2021.09.20
    '공부 및 정리/백준 코드' 카테고리의 다른 글
    • [C++]백준 - 5639번 문제
    • [C++]백준 - 2263번 문제
    • [C++]백준 - 1450번 문제
    • [C++]백준 - 1991번 문제
    Plite
    Plite
    개발 일지, 게임 이야기 등을 적어두는 공간입니다.

    티스토리툴바