o_onn5

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 512 MB 74073 37244 24264 49.197% 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 ..

https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 문제 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net DP 문제다. 아래의 점화식을 통해 풀 수 있는 문제다. dp[현재위치] += max(대각선 한 칸 뒤, 대각선 두 칸 뒤) 처음에는 아래와 같이 풀고 맞았겠거니 했는데 99%에서 틀렸다. t = int(input()) for _ in range(t): n = int(input()) arr = [list(map(int,input().split())) for _ in range(2)] d..

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 처음에는 접근을 BFS와 DP를 섞어서 하면 될 것 같은데? 했지만 메모리초과가 나왔다. BFS로 풀려고하면 생각보다 조건들이 까다로워져서 다른 방법을 생각해봤다. 그래서 생각해낸것이 이중 for문으로 전부 확인하면서 DP 돌리는거였다(진작에 이렇게 할걸..ㅋㅋㅋ) DP에는 해당 위치로 올 수 있는 경로의 개수를 저장한다. 그리고 이중 for문을 돌릴 시 맨 마지막 (n-1, n-1) ..

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 사용하는 횟수의 최솟값은 "1로 만들기"에서 이미 다뤘던 시리즈 문제다. 이번 문제는 연산이 진행되면서 방법에 포함된 수도 출력해야하는 문제다. 어려웠다면 아마 여기서 어려웠을 것 같다. 문제를 보자마자 DP 문제구나 싶었지만 BFS로도 풀 수 있을 것 같아서 BFS로 먼저 풀어봤다. Python으로 제출했더니 TLE가 나왔고 Pypy로 제출하니 통과된 코드다. from collections import deque n = int(input()) q = deque() q.append([n]) def bf..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 동전1 문제 풀면 동전2는 금방 풀 수 있다. 역시 재밌다. INF = 987654321 n,k = map(int,input().split()) coins = [] for _ in range(n): coins.append(int(input())) dp = [INF]* (k+1) dp[0] = 0 for coin in coins: for i in range(coin,k..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 최근에 DP를 배우고 DP문제에 재미들렸다. DP가 유독 생각하는 시간이 코드 수정하는 시간보다 많은 알고리즘인 것 같다. DP 코드가 대체적으로 길지 않은데 어렵다보니 매력적인 알고리즘이다. 이 동전 문제도 DP문제 중 대표적인 유형이라고 볼 수 있을 것 같다. 이전에 공부했던 내용이라 금방 풀었음. n,k=map(int,input().split()) coins = [] for _ in range..