본문 바로가기

알고리즘60

[Python] 백준 11058번: 크리보드 https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 1. dp의 값을 모두 1번의 경우 A로 출력할때만으로 초기화해준다. 2. 붙여넣기를 하려면 전체선택 + 복사가 필요하다. 현재 인덱스 기준으로 3번째 뒤부터 붙여넣기를 해주는 낮은 수부터 높은수 순으로 bottom-up 방식으로 진행해준다. n = int(inp.. 2021. 10. 14.
[Python] 백준 2616번: 소형기관차 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 1. 각 기관차 갯수마다 최대로 태울수있는 객차의 수를 구한다. 2. 점화식은 dp[i][j] = max(dp[i][j-1], dp[i-1][j-k] + sum(lst[j-k+1:j+1])) 이다. 현재 기관차의 갯수가 만약 2라고 가정할 때 이전까지의 값 dp[2][j-1] 과 dp[1][j-k] + 최대 객차의 수 를 비교한다. 35 40 50 10 30 45 60 1 75 90 90 9.. 2021. 10. 14.
[Python] 백준 2482번: 색상환 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 처음과 마지막이 (0, 0), (0, 1), (1, 0), (1, 1) 일때로 나누었다. (0, 0) 이면 dp[i][j-1]가 0으로 끝날때 + 0 (0, 1) 이면 dp[i-1][j-1]의 (0, 0)에 + 1, (1, 0) 이면 dp[i][j-1]가 1로 시작할때 + 0 (1, 1) 이면 dp[i-1][j-1]의 (1, 0)에 + 1 마지막에 (1, 1)인 경우만 제외하고 전부 더해준다. import sys .. 2021. 10. 13.
[Python] 백준 2688번: 줄어들지 않아 https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1 2021. 10. 13.

티스토리툴바