7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 냅색 응용문제. 아이디어 냅색 알고리즘의 기본 원리를 이용해 해결할 수 있다. 이차원 리스트 backpack[x][y]는 x번째 앱까지 y비용으로 얻을 수 있는 최대 메모리값이다. 1. 열의 크기는 제시된 모든 비용의 총합으로 한다. 2 - 1. 현재 앱의 비용 costList [i]가 j보다 크면 그대로 둔다. backpack[i][j] = backpack[i - 1][j] 2 - 2. j 가 더 크면 현재 앱의 유무를 비교해 값을 업데이트해준다. backpack[i..
2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 설탕 N킬로그램을 주고 이걸 5킬로그램, 3킬로그램 봉지로 가장 적은 개수로 나누는 문제. 처음에는 수학으로 해결하려다가 "동전" 문제가 생각나서 DP로 해결했다. 아이디어 n킬로그램은 (n - 3) + 3 또는 (n - 5) + 5로 생각할 수 있다. 따라서 n킬로그램의 봉지 개수는 n - 3과 n - 5 킬로그램 봉지 개수 중 작은 거(min) + 1이 된다. 이 아이디어로 해결하려면 n - 3과 n - 5의 개수 정보를 저장해 뒀다가 재사용이 필요하다. 3 ~ n킬로..
https://www.acmicpc.net/problem/28303 28303번: 자석 예제 1의 경우 N극이 3번 칸에 놓이고 S극이 5번 칸에 놓이도록 자석을 설치할 때 1번 현상으로 $a_3=22$의 에너지가 충전되며, 2번 현상으로 $a_5=4$의 에너지가 소모되고, 3번 현상으로 $(5-3)\times 2=4$ www.acmicpc.net N의 최댓값이 500,000이다. 시간제한은 2초나 되지만, N**2 같은 건 절대 안 된다. 이런 걸 고려해서 처음에는 DP, 그리디, 누적 합, 투포인터 등등 생각했었는데 1시간 정도 아이디어도 안 나왔다. 결국 알고리즘 분류를 확인했다. 누적 합 인걸 확인하고 최대한 누적 합 알고리즘을 적용하려고 했다. 코드 작성 중간에 내가 원하는 로직을 구현하기 위해..
https://www.acmicpc.net/problem/28017 28017번: 게임을 클리어하자 첫째 줄에 산지니가 게임을 몇 회차를 하는지 나타내는 수 $N$과 무기의 종류 $M$이 공백으로 구분되어 주어진다. $(2 \le N, M \le 500)$ 둘째 줄부터 $N$개의 줄에는 각 무기마다 게임을 클리어하는데 www.acmicpc.net 대회 초반에 삽집하다가 DP인걸 깨닫고 해결했다. pypy로 제출, 이후 python으로 다시 제출. 아이디어 1. 반복문 단순 반복문으로 작성했다 실패했다. 2. DP n회차의 각 무기마다 올 수 있는 시간을 저장하면 된다. 위 이미지처럼 이전 행에 있는 값 중 최솟값을 다음 행에 더해가며 업데이트하면 된다. 최종적으로 마지막 행의 최솟값을 출력하면 된다. 전..
https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 아이디어 1. 그리디와 dp 처음에는 n을 넘지 않는 최대 제곱수를 n에 빼가면 되지 않을까 생각했다. 이렇게 하면 예외가 생긴다. 예를 들어 12는 그리디로 생각하면 9, 1, 1, 1이지만 정답은 4,4,4로 3개가 최소 개수다. 다시 문제 내용을 보고 dp로 풀기로 결정 DP[n] = (n이라는 수를 만드는데 필요한 수의 개수) 코드 설명 k = 1 whi..
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net DP 너무 어렵다에요 아이디어 1. DP 문제를 보고 dp문제인 것도 알고 'DP [k] = 합이 k가 되는 경우의 수'라는 것도 알았다. 근데 점화식 아이디어가 떠오르지 않아 검색의 힘을 빌렸다. 일주일 뒤에 또 풀어봤는데 또 까먹었다. 이해를 못 했다는 뜻이다. 이번 기회에 제대로 이해하고 넘어가기로 함. 코드 설명 DP = [0] * (k + 1) DP[0] = 1 for c in coins:..
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 메모리 제한(4MB)이 있는 dp문제 아이디어 1. 메모리 제한 매우 적은 메모리 제한을 보고 dp를 사용하기로 결정 단순히 문제에 주어진 N값만 보고 배열을 만들기엔 4MB로는 턱없이 부족하다. 따라서 임시로 저장해주는 변수를 따로 만들어 사용 코드 설명 max_arr = [int(x) for x in sys.stdin.readline().rstrip().split()] min_arr = copy.copy(m..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이썬이라 억까당함. 난이도는 낮지만 시간 초과로 고생했다. 맨 처음 bfs로 풀었을때 시간 초과가 채점 70%에서 자꾸 걸리길래 방법이 틀린 줄 알았다. 아마 파이썬이 아니였으면 맞았을 거 같다. from collections import deque import sys count = 0 N = int(input()) home = [] for _ in range(N): h..
