Doby's Lab

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 0 이후에는 0~9 사이의 수 1 이후에는 1~9 사이의 수 ... 이와 같은 규칙이 존재하는 것을 알고 2차원 배열을 선언하여 cache[n번째 자릿 수][0~9사이의 수]로 선언하고, [n - 1번째 자릿수]가 [0~9사이의 수 중 하나]일 때 몇 가지 수가 나올 수 있는지 계산해주면 된다. [점화식] (n != 1 && n != 2)일 때 다음을 만족한다...

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 지난번에 풀었던 RGB 거리 문제와 다른 조건이 딱 하나 걸려있다. (RGB 거리 https://draw-code-boy.tistory.com/51) 1번 집과 N번 집의 색깔이 같으면 안 된다. 이 조건을 맞춰주기 위해 초기값(1번 집)에서 최솟값이 나오는 인덱스를 구하고, DP가 끝난 후에 최솟값이 나오는 인덱스 값(1번 집 색깔)을 제외한 색깔 중에 DP 최솟값을..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 저번에 공부했던 LCS알고리즘을 이해하고 있다면 똑같은 DP의 방식으로 문자열 배열 DP를 돌리면 된다. (LCS 정리 https://draw-code-boy.tistory.com/126) [AC 코드] cache2 == 문자열 메모이제이션 배열 #include #include #include #include #define MAX 1000 + 1 #..

https://www.acmicpc.net/problem/15489 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net 파스칼 삼각형의 이항 계수의 특성상 r번째 행, c번째 열은 (r - 1)C(c - 1)과 같음을 이용하여 풀면 된다. 그리고, 이중 for문을 이용하여 변 w 길이를 만족하게끔 최종합에다가 (r - 1)C(c - 1)을 더해주면 된다. [AC 코드] #include #include #define MAX 30 + 1 using namespace std; int cache[MAX][MAX]; int combi(int ..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 우선, 글에 들어가기 앞서 포스팅의 제목에서 '수열'이라고 강조한 이유는 '문자열'과 '수열'은 다른 의미이기 때문이다. 저번에 LIS를 포스팅하면서는 수열과 집합의 차이를 느꼈는데 이번 키워드에서는 문자열과 수열의 차이를 알아야 한다. (집합에 관해 적은 포스팅: https://draw-code-boy.tistory.com/85) [문자열 vs 수열]..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 다리를 잇는 경우가 고등학생 때 배우던 조합론: 콤비네이션을 기억해낼 수 있다면 풀릴 수 있는 문제였다. 시간도 0.5초로 짧아서 탑 다운 DP형식으로 구현을 했고 범위는 30 이전이라 문자열의 합은 구현하지 않아도 될 거 같았다. 콤비네이션에 관한 문제를 예전에 풀고, 포스팅해놓았어서 쉽게 풀렸다. https://draw-code-boy.tistory.com/101 [알고리즘] 백준 2407번:..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 노트에 구현을 해보았다. 시작 수가 0이면 안 되기 때문에 1 ~ 9까지 수들을 각 수로부터 파생될 수 있는 수들을 트리 형식으로 그려볼 수 있었다. 다음과 같은 특징을 지니고 있었다. 시작 수는 0이 될 수 없다. 1 ~ 8까지는 두 가지의 수가 파생될 수 있다. 0과 9는 각각 1, 8 밖에 파생시키지 못한다. 이러한 관계식을 어떻게 나타낼 수 있을까 한참을 고민하다가 2차원 배열을 떠올렸다. cache[i번째 자리][숫자 j] = 숫자 j가 나온 횟수; 다음 계단식의 특징을 가지고서 점화식을 나타내면 //..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 여전히 DP 문제는 접근하기 어렵다. 문제를 풀 때마다 '이렇게 생각해보자'라는 지난 DP 문제로부터 나름대로 얻은 팁을 적용해봐도 어렵다. 이제까지 접근했던 방식들을 떠올려보면 직접 TC를 가지고서 output을 노트에 도출하며 관계성과 점화식을 세웠었다. [input] 6 6 10 13 9 8 1 [answer] 33 맨 처음에는 조금 멍청하게 접근을 했는데 n번째 포도주를 선택한다고 했을 때,..