Doby's Lab

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/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net 연산자 배열을 선언 후 각 연산자를 고른 경우 총 4가지를 가지고서 백트래킹 하면 된다. #include #include #include #include #include using namespace std; int n; vector num; int oper[4] = { 0, }; int maxValue = INT_MIN; int minValue = INT..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 범위가 8밖에 되지 않아서 백트래킹으로 나올 수 있는 수열들을 temp 배열에 담아 직관적으로 풀 수 있는 문제였다. abs() == 절댓값 함수 #include #include #include #define MAX 8 + 1 using namespace std; vector v; vector temp; int n; bool visited[MAX]; int maxValue = 0; void sol(vector&..

https://www.acmicpc.net/problem/10769 10769번: 행복한지 슬픈지 승엽이는 자신의 감정을 표현하기 위해서 종종 문자 메시지에 이모티콘을 넣어 보내곤 한다. 승엽이가 보내는 이모티콘은 세 개의 문자가 붙어있는 구조로 이루어져 있으며, 행복한 얼굴을 나 www.acmicpc.net 공백 포함하기 위해 문자열 함수 getline() 사용 #include #include using namespace std; int main(){ string value; getline(cin, value, '\n'); int h = 0; int s = 0; for(int i = 0; i = value.size() - 2){ continue; } i..

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/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 n r이 nCr이라는 것을 알면 예전에 풀었던 문제와 똑같이 풀린다. 다른 점은 나머지 정리(MOD == 10007)로 인해 문자열의 합을 구할 필요 없다는 점이었다. (콤비네이션 예전 포스팅 https://draw-code-boy.tistory.com/101) [AC 코드] #include #include #define MOD 10007 using namespace std; int cache[1001][1001]; int combi(int n, int r..

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 수열]..