본문 바로가기

dp11

[백준/파이썬] 15486: 퇴사 2 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 요약 : 상담일을 하는 백준이는 N+1일 째 되는 날 퇴사를 한다. 남은 N일 동안 최대한 많은 상담을 하려고 한다. 이때 백준이가 얻을 수 있는 이익을 구하여라. 예제 입력 1 7 3 10 5 20 1 10 1 20 2 15 4 40 2 200 예제 출력 1 45 시도 ) 보자마자 dp문제라는 느낌이 왔다. 날짜의 개수만큼 dp를 생성해주고, T와 P를(상담걸.. 2023. 4. 19.
[백준/파이썬] 10942: 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 요약 : N개의 자연수를 가지고 M가지 질문을 한다. 시작점과 끝점이 주어졌을 때 N이 그 지점 사이에서 팰린드롬을 만족하면 1을 출력, 아니면 0을 출력한다. 예제 입력1 7 1 2 1 3 1 2 1 4 1 3 2 5 3 3 5 7 예제 출력1 1 0 1 1 약 1년전에 풀었던 문제인데도, 꽤 애를 먹었다. 요며칠 문자열 문자만 풀어서 그냥 아무생각없이 list reversed를 썼다가 시간초과가 떴다. dp문제임을 힌트로 얻고.. 2023. 4. 17.
[백준/파이썬] 9657: 돌 게임3 https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 문제 요약 : 돌 N개가 있다. 상근과 창영은 턴을 번갈아가며 돌을 1,3,4개 중 골라 가져갈 수 있다. 마지막으로 돌을 가져가는 사람이 이긴다. 예제 입력 1 : 6 예제 출력 1 : SK 📌 풀이 ) 문제의 규칙을 알아내기 위하여 일단 쭉 작성해보았다. 상근이가 이기면 1, 창영이가 이기면 0을 작성하였다. dp[1] = 1 dp[2] = 0 dp[3] = 1 dp[4] = 1 dp[5] = 1 dp[6] = 1 dp[7] = 0 dp[8] = 1 dp[9] = 0 dp[10] = 1 dp[1],dp[3],d.. 2023. 4. 11.
[백준/파이썬] 1463 : 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 요약 : 3으로 나누어 떨어지면 3으로 나눈다. 2로 나누어 떨어지면 2로 나눈다. 1을 뺀다. 이 세가지 연산을 사용하여 정수X(1이상 10^6이하)를 1로 만드는 최소한의 횟수 풀이 ) 1000000 이하면 dp를 1000001개 만들어줘야하는데 그대로 1000000개만 만들어서 IndexError가 떴었다. 실수를 줄이자.. 문제에서 주어진 힌트를 보면 10의 경우10 → 9 → 3 → 1 로 3번 만에 만들 수 있다. dp와 min을 통해 풀 수 있는 문제 dp = [0 for _ in range(.. 2023. 2. 27.
[백준/파이썬] 2091 : 동전 https://www.acmicpc.net/problem/2091 2091번: 동전 첫째 줄에 답을 출력한다. cent의 수, nickel의 수, dime의 수, quarter의 수를 출력한다. 불가능한 경우에는 0을 네 개 출력한다. www.acmicpc.net 문제 요약 : 1,5,10,25 동전이 있다. 각 동전의 개수는 정해져 있고, 동전 개수 내로 X원을 만드는 가장 큰 경우의 수를 출력하라. 동전 시리즈 풀겠다고 했다가 동전한테 털림 18번의 시도 끝에 성공한거라 어떻게 성공한건지 기록해놓으려고 한다,, 어디가 틀렸는지 반례라도 알고 싶어서 검색을 많이 했는데, 파이썬으로 2091번을 푼 경우가 거의 없었고 질문도 답해주신 분들이 없었다. 그나마 검색에서 나오는 경우는 DFS였는데, 나는 DF.. 2022. 10. 25.

티스토리툴바