본문 바로가기

Algorithm/DP(Dynamic Programing)

 (72)
(C++) - 백준(BOJ) 1932번 : 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net dp 문제입니다. 풀이방법 d[i][j] : 현재 i행, j열로 왔을 때 최댓값입니다. i행 j열로 오기 위해서는 이전 위치가 i-1행 j-1열 또는 i-1행 j열뿐입니다. 따라서 해당위치의 최댓값 + triangle[i][j]가 답이 됩니다. 점화식으로 쓴다면, d[i][j] = max(d[i-1][j-1],d[i-1][j]) + triangle[i][j] Code #include using namespace std; int n, triangle[505][505], ..
(C++) - 백준(BOJ) 5557번 : 1학년 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net dp로 해결한 문제였습니다. 풀이방법 d[i][j] = +또는 -인 수식을 i개 뽑았을 때 j수를 만드는 경우의 수로 정의합니다. i를 n-2개 뽑았을 때 j가 마지막 카드에 도달했다면 경우의 수를 1늘려줍니다. Code #include #define ll long long using namespace std; ll n, num[101], d[101][101]; ll dp(int i, in..
(C++) - 백준(BOJ) 1256번 : 사전 https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net dp로 푼 문제였습니다. 풀이방법 1. d배열 : i개의 a와 j개의 z로 만들 수 있는 문자열의 개수로 정의합니다. 점화식으로 다음과 같이 표시됩니다. d[i][j] = min(d[i][j], d[i-1][j] + d[i][j-1]) 2. 최대한 'a'를 앞에 붙여줘야합니다. Code #include using namespace std; string word; //i개의 a와 j개의 z로 만들 수 있는 문자열의 개수 int d[101][101..
(C++) - 백준(BOJ) 15989번 : 1, 2, 3 더하기 4 https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net dp문제였습니다. 풀이방법 특정한 규칙을 수학적으로 찾으면 답을 도출할 수 있습니다. 1111은 22로 교체될 수 있습니다. 222는 33으로 교체될 수 있습니다. 적절히 규칙을 찾으면 점화식을 구할 수 있습니다. Code(Top down, 주석은 bottom up) #include #define ll long long using na..
(C++) - 백준(BOJ) 16195번 : 1, 2, 3 더하기 9 https://www.acmicpc.net/problem/16195 16195번: 1, 2, 3 더하기 9 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이하 이어야 한다. www.acmicpc.net dp로 해결한 문제였습니다. 풀이방법 1,2,3을 이용해 i이라는 숫자를 j개로 만들기 위한 점화식은 다음과 같습니다. d[i][j] = d[i-1][j-1] + d[i-2][j-1] + d[i-3][j-1] 1을 사용했을 때 숫자를 1개를 소모한 경우 + 2를 사용했을 때 숫자를 1개 소모한 경우 + 3을 사용했을 때 숫자를 1개 소모한 경우라고 풀어서 쓸 수 있습니다. Code(Bottom Up..
(C++) - 백준(BOJ) 15592번 : 1, 2, 3 더하기 7 https://www.acmicpc.net/problem/15992 15992번: 1, 2, 3 더하기 7 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다. www.acmicpc.net dp 문제였습니다. top-down으로 해결했습니다. 풀이방법 1,2,3을 이용해 i이라는 숫자를 j개로 만들기 위한 점화식은 다음과 같습니다. d[i][j] = d[i-1][j-1] + d[i-2][j-1] + d[i-3][j-1] 1을 사용했을 때 숫자를 1개를 소모한 경우 + 2를 사용했을 때 숫자를 1개 소모한 경우 + 3을 사용했을 때 숫자를 1개 소모한 경우라고 풀어서 쓸 수 있습니다. Cod..
(C++) - 프로그래머스(Summer/Winter Coding(~2018)) : 스티커 모으기(2) https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr dp문제였습니다. 풀이방법 greedy하게 띄엄띄엄 최대한으로 스티커를 떼어나면 최대일 것 같으나 그렇지 않습니다. 특정한 스티커가 점수가 나머지보다 월등히 높은 경우 그 스티커를 무조건 1개씩 건너뛰면서 떼어낼 경우 그 스티커를 떼지 못할 수 있습니다. 따라서 dp를 사용해야 합니다. 1. sticker의 size가 1인경우엔 바로 점수를 반환..
(C++) - 프로그래머스(연습문제) : 멀리 뛰기 https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr dp문제였습니다. 풀이방법 1칸 또는 2칸을 뛰므로 n에 도착하기 위한 경우의 수 점화식은 다음과 같습니다. D[n] = D[n-1] + D[n-2] Code #include #define MOD 1234567 using namespace std; using ll = long long; ll d[2001]..

티스토리툴바