[백준] 17070 파이프 옮기기 1, python
https://www.acmicpc.net/problem/17070처음에는 백트래킹으로 해결하려 했다가 시간초과가 났다. → 다음에는 →, ↘↓ 다음에는 ↓, ↘ ↘ 다음에는 →, ↘, ↓ 로 옮길 수 있다.반대로→이전에는 →, ↘ ↓ 이전에는 ↓, ↘↘ 이전에는 →, ↘, ↓ 만 가능하다. →를 0, ↓를 1, ↘를 2라고 하고 dp [i][j]를 파이프의 오른쪽 끝의 위치가 i, j일 때 옮길 수 있는 경우의 수라고 하면 dp [i][j][현재방향] = sum(dp [현재방향에 따른 이전 파이프 위치][ 현재방향에 따른 이전 파이프 위치 ][이전방향]) 가 된다. 따라서 현재방향에 따라 3가지 경우로 나눈뒤에 dp를 갱신해 주면 된다. import syssys.setrecursion..
[백준] 13904 과제, python
https://www.acmicpc.net/problem/13904 처음에는 백트래킹과 dp를 사용해서 해결하려 했는데 시간초과가 났다.힙을 사용해서 간단하게 풀수 있는 문제였다.최소힙에 과제 점수를 넣고, 힙의 길이가 마감까지 남은 일수보다 클 경우 최솟값을 제거한다.최종적으로 마지막까지 힙에 남은 값들을 더해주면 된다.마감일까지 남은 일수(d)과제점수(w)최댓값이 되게 선택 하는 경우 설명120201일차에는 1개까지 가능하므로 20 추가25020, 50마찬가지로 50 추가33020, 30, 5030 추가41010, 20, 30, 5010 추가44020, 30, 40, 504개까지 밖에 수행할수 없으므로 가장작은 10을 빼고 40을 추가46030, 40, 50, 60마찬가지로 20을 빼고 60을 추가6..
[백준] 12738 가장 긴 증가하는 부분 수열 3, python
https://www.acmicpc.net/problem/12738 LIS(가장 긴 증가하는 부분 수열), python LIS(가장 긴 증가하는 부분 수열), python가장 긴 증가하는 부분 수열이란? 가장 긴 증가하는 부분 수열, LIS(Longest Increasing Subsequence) 란 오름차순으로 정렬된 부분 수열 중에 가장 긴 것을 말한다. 예를 들면 수열이 [10, 20, 5, 30, 15, 50]에서aiden0413.tistory.com LIS (Longest Increasing Subsequence)를 구하는 문제이다. n이 크기에 O(n²)로 풀면 시간초과가 나온다.수열을 저장할 배열을 만든다. 수열에서 하나씩 탐색하며 배열이 비어있거나, 넣으려는 수열의 값이 배열의 마지막..