분류 전체보기45 [백준 14003] 가장 긴 증가하는 부분 수열 5 https://www.acmicpc.net/problem/14003 해설 이번 문제는 LIS의 끝판왕 가장 긴 증가하는 수열 5 문제이다. 역시 쉽지 않았다. https://far-simple.tistory.com/43 전에 썼던 이 방법을 사용했다. ˙˙˙ 소스코드 #include #include #include using namespace std; int n, arr[1000001], p[1000001], cnt; vector ans, print; int main(){ cin >> n; for (int i = 1; i > arr[i]; ans.push_back(arr[1]); for (int i = 2; i = 0; i--) cout 2020. 4. 2. [백준 12015] 가장 긴 증가하는 부분 수열 2 https://www.acmicpc.net/problem/12015 해설 이번 문제는 LIS 문제인데, 내가 아는 LIS 소스코드와 다르게 풀어야 해서 한번 가져와봤다. 좀 고급 LIS 느낌이다. #include #include using namespace std; int dp[1001]; int num[1001]; int main() { int n; cin >> n; for (int i = 0; i > num[i]; int res = -1; for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) if (num[j] < num[i]) dp[i] = max(dp[i], dp[j] + 1); res = max(re.. 2020. 4. 2. [백준 2565] 전깃줄 https://www.acmicpc.net/problem/2565 해설 이번 문제는 LIS 를 이용 해 풀었다. 푼 방법은 일단 A를 기준으로 정렬하고, A와 연결 된 B에 대해서 LIS를 때려주었다. 거기서 나온 LIS를 n에서 빼주어 답을 내었다. ˙˙˙ 소스코드 #include #include #include using namespace std; int dp[1010]; int arr[101]; int main() { pairvp[101]; int n; cin >> n; for (int i = 0; i > vp[i].first >> vp[i].second; sort(vp, vp + n); int res = -1; for (int i = 0; i < n; i++) { dp[.. 2020. 4. 1. [백준 5397] 키로거 https://www.acmicpc.net/problem/5397 해설 이번 문제를 벡터로 푸실려는 분들이 많은 텐데, 아마 시간 초과 뜰 확률이 높다. 나는 시간 초과를 방지 해 원소의 삽입이 빠른 덱으로 풀었다. (다른 블로그보면 스택으로도 풀고, 리스트로도 풀고 여러 가지 방법으로 푼 거 같다.) ,-와 같이 커서를 신경써야하기 때문에 커서를 cur로 두고 풀었다. ˙˙˙ 소스코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; while (n--) { string tt; cin >> tt; deque st; int cur = 0; for.. 2020. 3. 31. 이전 1 2 3 4 5 ··· 12 다음
