[백준] 2352 반도체 설계 (LIS)
2020. 1. 17. 16:00
https://www.acmicpc.net/problem/2352
2352번: 반도체 설계
첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.
www.acmicpc.net
LIS, 동적계획법, 그리디 알고리즘 등으로 풀수 있는 문제입니다.
저는 LIS로 접근해봤습니다.
첫번째 원소를 결과배열에 넣고 시작합니다.
두번째 원소부터 배열의 마지막 값과 비교해서 해당원소가 더 크면 뒤에 추가,
작으면 앞에서부터 해당 원소보다 처음으로 같거나 큰 배열값을 만났을때 교체 하는 식으로 접근했습니다.
포트번호가 4 2 6 3 1 5
에서 가장긴 증가하는 부분수열을 구하면
2 3 5가 되는데 이번 문제를 푸는 방식으로 구해보면 1 3 5 가 나옵니다.
선이 겹치지 않아야 하는데 이 부분에서 고민이 많이 됐습니다.
답은 최대 길이만 구하면 되므로 통과되는데 선의 겹침을 해결하지는 못했습니다.
이 부분을 고민중입니다..
'Algorithm & Data Structure > BOJ' 카테고리의 다른 글
| [백준] 1904 01타일 (Dynamic programming) (0) | 2020.01.22 |
|---|---|
| [백준] 4963 성의 개수(BFS) (0) | 2020.01.20 |
| [백준] 2644 촌수계산 (BFS) (0) | 2020.01.16 |
| [백준] 14888 연산자 끼워넣기 (BruteForce, 재귀호출) (0) | 2020.01.15 |
| [백준] 3053 택시 기하학 (0) | 2020.01.15 |