MG

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 한 숫자를 정했을 때 그 위의 두 경로 중 가장 최대값을 정하는 문제이다. 양 끝에 위치하는 숫자일 경우 바로 위 하나의 경로만 더하고 나머지 경우는 dp로 저장한 두 최대 경로 중 더 큰 값을 저장한다. #include #include #define MAX 501 using namespace std; vector v[MAX]; int dp[MAX][MAX]; int n, tmp, ans; int main() { ios::sync_with_stdio(0); cin.ti..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 파티하는 집 x가 주어졌을때 각 집에서 x로 갔다오는 최단거리를 모두 구하고 그 중 최대값을 묻는 문제이다. 한 정점으로부터 모든 정점으로의 최단거리를 구하는 다익스트라를 이용하면 된다. 하지만 주의할 점으로 여기서는 i에서 x로 가고 x에서 i로 가는 두 방향에 대해서 최단거리를 구해야 한다는 것이다. 여기서 문제를 조금 바꿔 해석하면 쉽게 되는데 우선, x에서 모..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 서로 이웃한 집과 같은 색이 아니면 된다. 그래서 n개의 집을 3가지 색으로 칠하는 dp[n][3]를 정의한다. 이를 0부터 n - 1까지 그리고 RGB 순으로 반복을 돌린다. k번째 집을 RGB 3종류로 칠한다고 각각 가정하고 이와 다른 색들로 칠해진 k - 1번째 집들 중 최소를 찾아 그 집을 칠할 때 드는 비용과 더해준다. 그리고 마지막에 최소값을 찾아 출력한다. #in..

https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 다음 수를 더하고 빼는 경우의 수를 계속 세나가야 하는 DP 문제이다. dp[i][j]는 i번째 수까지 계산에 넣었을 때 그 합이 j가 되는 경우의 수이다. n번째 수를 계산에 넣기 전에 dp[n-1]를 0부터 20까지 돌려 n번째 수를 더하거나 뺐을 떄 0 이상 20 이하이면 경우의 수를 더해주면 된다. #include #define MAX 101 using namespace std; l..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 이 문제의 요점은 같은 파티에 한 번이라도 속한 사람은 전부 통한다는 것이다. 예를 들어 1번이 진실을 알고 있고 2번이 한번이라도 1번과 같은 파티에 참석했으면 순서에 상관없이 다른 파티에서는 2번은 진실을 아는 사람처럼 행동하게 된다. 그렇기에 이 문제는 한 번이라도 같은 파티에 참석해봤냐 안 해봤냐 나누는 문제로 Union-Find 알고리즘을 사용하면 된다. 더 자세히 말하자면 각 파티당 참여하는 인원..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 배낭문제와 유사한 풀이방식이다. dp[k]는 k원이 되는 동전의 구성 경우의 수이다. 이를 중복없이 계산하기 위해서 1번째 동전을 1~k원까지 채워넣고 그리고 2번째, 3번째 ... n번째 동전까지 경우의 수를 고려한다. 그렇게 되면 j번째 동전에서 그 전 동전이 이미 반영이 다 되고 더 이상 반영이 안되기에 중복이 안되게 된다. 그래서 dp[j]에 dp[j - arr[i]] 를 계속 더해주고 dp..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 전형적인 dp문제이다. dp[i]는 i번째 포도주에 도달했을때 가장 많이 마신 양이다. 그렇다면 두 가지 방법으로 나뉠 수 있다. 첫번째로 i번째를 마셨을때이다. 이를 마셨다면 또 두가지로 나뉜다. 이전 포도주를 마셨냐 안 마셨냐이다. 마셨다면 3번 연속으로 못 마시기에 dp[i - 3]과 이전 포도주, 현재 포도주를 다 더해준다. 이전 포도주를 안 마셨다면 dp[i - 2]와 현재 포도주를 더해준..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 얼핏 보면 간단한 조합 구현 문제이지만 범위를 봐야합니다. 최대값인 100_C_50 는 long long int 의 범위를 거뜬히 넘어버려 계산식으로만 하면 틀립니다. 그렇기에 string으로 구현해 줍니다. 기본적으로 dp를 베이스로 nCm = n-1Cm-1 + n-1Cm 을 이용하여 재귀를 돌려줍니다. n = m or m = 0 일 때 1을 반환하고 이 전의 값이 있으면 그대로 반환해줍니다. 그리고 이 두 값을 더할 때 string의 첫째자리만 더해서 문자열로 추가하는 방식으로 정답을 string으로 반환합니..