[실버2] 11053번 : 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053dpi는 arri를 마지막 원소로 가지는 부분 수열의 최대 길이라고 정의하면,0 <= j < i에 대하여, dpi = max(dpi, dpj + 1) if arrj < arri

2021년 4월 11일
·
0개의 댓글

[골드3] 15483번 : 최소 편집

https://www.acmicpc.net/problem/15483바꾸기 전 문자열을 행 크기, 바꾼 후 문자열을 열 크기로 삼은 2차원 리스트 dp를 만들어주었다만약 행과 열에 해당하는 문자열이 같다면 왼쪽 위에 해당하는 수를 그대로 대입하고,다르다면 왼쪽(

2021년 4월 11일
·
0개의 댓글

[실버4] 14501번 : 퇴사

https://www.acmicpc.net/problem/14501리스트를 뒤에서부터 확인하면서 해당시간 i에서 ti만큼 시간이 흘렀을 때, 값이 n보다 작거나 같으면 dp 점화식에 따라 최고 이익을 갱신해주었다소스 코드

2021년 4월 11일
·
0개의 댓글

[플래티넘5] 12920번 : 평범한 배낭2

https://www.acmicpc.net/problem/12920중복되는 물건 또한 개별의 물건으로 처리하여 2차원 dp 리스트를 통해 해결하려 했지만 시간초과로 인해 할 수 없었다다른 사람들의 풀이를 참조하였고, 비트마스크 개념을 사용하는 문제임을 알 수

2021년 4월 10일
·
0개의 댓글

[골드3] 1005번 : ACM Craft

https://www.acmicpc.net/problem/1005dp를 적용하여 구하는 위상정렬 문제였다q에서 값을 뺄 때, 진입차수-1과 동시에 dpnow(이전 건물까지 걸리는 시간)+di(이번 건물을 짓는 시간)와 dpi 중 더 큰 값을 dpi에 저장해주었

2021년 4월 5일
·
0개의 댓글

[실버1] 1309번 : 동물원

https://www.acmicpc.net/problem/1309n줄에 사자를 하나도 배치하지 않을 경우의 수, n줄 왼쪽에 사자를 배치할 경우의 수, n줄 오른쪽에 사자를 배치할 경우의 수를 합산하여 구할 수 있었다소스 코드

2021년 4월 1일
·
0개의 댓글

[실버3] 1699번 : 제곱수의 합

https://www.acmicpc.net/problem/1699처음에 짠 코드는 시간초과가 났었다...다른 사람의 풀이를 참고해 효율적으로 문제를 풀 수 있었다소스 코드

2021년 4월 1일
·
0개의 댓글

[골드5] 2225번 : 합분해

https://www.acmicpc.net/problem/2225규칙을 쉽게 생각해내지 못해서 어려웠던 문제다예를 들어 n=2, k=3인 경우에는(0을 1개의 숫자로 만드는 경우의 수 x 2를 2개의 숫자로 만드는 경우의 수)\+(1을 1개의 숫자로 만드는 경

2021년 3월 30일
·
0개의 댓글

[실버2] 1912번 : 연속합

https://www.acmicpc.net/problem/19122차원 리스트에 연속수열의 갯수별로 저장하는 점화식을 세웠는데 메모리 초과가 나서 문제를 해결할 수 없었다...풀이를 찾아본 결과, 아주 간단하게 문제를 해결할 수 있었다효율적인 해결방안으로 문제

2021년 3월 29일
·
0개의 댓글

[Level2] 가장 큰 정사각형 찾기

https://programmers.co.kr/learn/courses/30/lessons/12905

2021년 3월 28일
·
0개의 댓글

[골드5] 12865번 : 평범한 배낭

https://www.acmicpc.net/problem/12865전형적인 dp문제였지만 점화식을 세우는 것이 어려웠다...dp 유형에 더욱 익숙해지도록 노력해야겠다소스 코드

2021년 3월 28일
·
0개의 댓글

[골드4] 1520번 : 내리막 길

https://www.acmicpc.net/problem/1520dfs/bfs로 풀어야겠다는 생각은 했지만 dp랑 어떻게 연결해서 풀어야할지 생각하기가 조금 어려웠던 문제다dfs 함수에서 현재 좌표를 기준으로 상하좌우 확인했을 때, 이동이 가능하면 dfs 함수

2021년 3월 28일
·
0개의 댓글

[실버1] 10844번 : 쉬운 계단 수

https://www.acmicpc.net/problem/10844오르막 수 문제와 비슷한 방식으로 해결할 수 있었다다만, 0과 9는 차이나는 수가 1개씩밖에 없으므로 따로 처리를 해주어야 했다소스 코드

2021년 3월 28일
·
0개의 댓글

[실버1] 11057번 : 오르막 수

https://www.acmicpc.net/problem/11057i는 자릿수 j는 마지막 수로 설정하여 dpi에는 j보다 작거나 같은 수들인 k를 저장하도록 하였다소스 코드

2021년 3월 28일
·
0개의 댓글

[실버1] 2294번 : 동전2

https://www.acmicpc.net/problem/2294동전 사용 개수의 최솟값 저장을 위해 dp를 100001로 초기화해주었다동전 단위를 하나씩 사용하면서 최솟값을 갱신해주는 점화식을 세웠다소스 코드

2021년 3월 27일
·
0개의 댓글

[실버1] 2293번 : 동전1

https://www.acmicpc.net/problem/2293dp를 사용해야 하는 건 알았는데 점화식을 세우는 것이 어려웠다(단순하게 생각할 문제가 아니었음...)동전 단위를 하나씩 사용하면서 모든 금액에 해당 동전을 사용했을 경우를 dp에 축적해주었다소스

2021년 3월 27일
·
0개의 댓글

[Level4] 도둑질

https://programmers.co.kr/learn/courses/30/lessons/42897현재 집을 도둑질 하거나 하지 않을 경우로 나누어,dpi = max(dpi-1, dpi-2 + moneyi)와 같은 점화식을 세울 수 있었다처음에는 원형을 일자

2021년 3월 26일
·
0개의 댓글

[Level3] N으로 표현

https://programmers.co.kr/learn/courses/30/lessons/42895예를 들어 dp3(= N을 3번 사용)은 N의 길이가 3인 경우(NNN), dp0과 dp1을 사용하는 경우로 생각할 수 있다따라서 dp를 사용해 문제를 풀었고,

2021년 3월 26일
·
0개의 댓글

[골드3] 2533번 : 사회망 서비스(SNS)

https://www.acmicpc.net/problem/2533처음에 단순히 bfs로 풀기 위해 시도했는데 엄청난 시간초과로 인해 제대로 된 코드인지조차 확인할 수가 없었다...그래서 다른 사람의 풀이를 참고하였고, dp를 사용해서 문제를 해결했다우선 문제

2021년 3월 26일
·
0개의 댓글