https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 길이가 N인 오르막수의 개수를 구하는 문제 -> 길이가 1~N인 오르막수의 개수를 모두 구해보자. 표를 만들어서 해보면 큼큼 굉장히 지저분하지만, 딱 알 수 있다. dp의 행 i는 1~N까지의 길이, 열은 j로 끝나는 수를 말한다. 즉, dp[i][j]는 i길이의 오르막 수 중에서 j로 끝나는 수의 개수 여기서 관건은 사실 i, j를 선언하는 것이다. j를 개념..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net DP는 그 안에서도 굉장히 많은 유형이 있다고 생각한다. 이 문제는 DP 기본 문제 중 하나라고 생각하는데, 조건이 추가된 것도 그렇고, 작은 문제에서 큰 문제로 가는 방식도 그렇고. 정말.. 어렵다~ DP 우선 문제를 정리해 보자면, N번째 계단에 최댓값으로 올라가야 한다. 이동 방법은 1) 1칸 이동 2) 2칸 이동 중요한 게 바로 조건! 연속 3칸을 밟으면 안 된다. DP는 N보다 작은 애들의 결과로 N..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 일반적인 dp 유형 문제인 것 같은데 굉장히 헷갈렸다. 이렇게 구상했다. 가장 헷갈렸던 것이 바로 dp의 정의였다. 여기서 dp는 i장 카드를 살 때의 최대 비용을 저장하는 배열로 사용한다. dp가 그렇듯 앞에 작은 문제들의 답으로 큰 문제의 답을 해결할 수 있도록 해야 하는데, 여기서는 카드 N장을 구매할 때의 최대 비용을 구해야 하므로, 1장~N-1장을 구매했을 때의 최대 비용부터 차례대로 구하면서 ..

https://www.acmicpc.net/problem/16974 16974번: 레벨 햄버거 상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, www.acmicpc.net 골머리 썩혔던 문제..^^ 처음에는 문제를 DP로 문자열을 계속 추가해서 진행했는데, 마지막 예제 입력인 50 4321098765432109 여기서 출력 값이 도저히 안 나와서 이렇게 하면 안 되는구나 싶었다. N이 50보다 작거나 같은 값이길래 될 줄 알았지.. X값이 저럴 줄이야... 사실 어떻게 하면 좋을지 모르겠어서 구글링을 해봤다. 다른 사람들은 어떻게 했는지 확인하기 위해..

https://school.programmers.co.kr/learn/courses/30/lessons/12913 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음에는 백트래킹으로 풀려고 했는데 생각보다 잘 안돼서 다시 생각해봤다. 우선, 같은 열을 포함하면 안된다. 아래 행으로 내려가면서 값을 더해야 하는데 그러면 맨 마지막 행에 값이 모이게 되는 것 아닌가? 그러면 이렇게 해보자. 1행은 0행의 다른 열 중 가장 큰 값을 더해주자. 이런 식으로 쭉 0열부터 3열까지 계산을 해주면 마지막 행의 열들을 모두 비교해서 가장 큰 값을 출력하면 된다! #in..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 2xn 스티커가 있고, 각 스티커에는 숫자가 적혀있다. 해당 스티커를 떼면 그 숫자를 얻을 수 있다. 숫자의 합이 최대가 되도록 스티커를 떼어내야 한다. 뗄 수 있는 스티커의 점수의 최댓값을 출력해라. 여기서 뗀 스티커의 상하좌우로 붙은 스티커는 뗄 수 없다. 2xn스티커이므로 2xi 스티커라고 가정하고 하나씩 차례대로 최댓값을 구해보자. dp[i][0] = i열의 0행 스티커를 떼어냈..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net Nx2 우리가 있고 가로/세로 붙여서 사자를 배치하면 안 된다. 이 우리에 사자를 배치하는 경우의 수를 구하라. N 줄의 우리가 있으니까 i(1~N) 개일 때 경우의 수를 모두 차례대로 구해보면 된다. 1x2 우리에서 사자를 배치하는 경우는 (1,0), (0,1), (0,0) 세 가지 경우가 있다. 이를 토대로, 마지막 줄에 위 세가지 경우를 포함한 경우의 수를 세보면 규칙이 나타난다. i=2일 때는 (1,0)와 (0,1)의 경우는 2가지 (0,0)의 경우는 3가지 i=3일 때는 (1,0)와 (0,1)의 경우는 5가지 (0,0)의..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net N잔의 포도주가 있다. 연속 3잔은 마실 수 없고, 가장 많은 포도주를 마실 수 있도록 해야 한다. 마신 총포도주의 최댓값 출력하라. 이 문제는 BOJ 2579: 계단 오르기 문제와 유사하다! 그러나 여기서는 두 잔을 연속으로 안 마실 수 있다는 점이 다른데, 이 부분이 헷갈렸다.ㅠ0ㅠ 1. dp 이차원 배열을 정하기 dp[i][0] = i-1번째 잔을 마시는 경우 dp [i][1] = i-1번째 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net N개의 집이 있고, 1부터 N까지 순서대로 집이 나열되어있다. 모든 집을 RGB 중 하나의 색상으로 칠하는데 드는 최소 비용을 출력하는 문제이다. RGB 색상을 고르는 것에는 규칙이 존재한다. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않..