목록분류 전체보기 (217)
Study hard
www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net [풀이] 재귀 DP로 풀 수 있는 문제였다. DP[i][j] : i번째 행렬부터 j번째 행렬까지 곱하는데 필요한 곱셈 연산의 최솟값 점화식 DP[i][j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + Matrix[i].r*Matrix[k].c*Matrix[j].c) #include #include //memset #include //min #include using na..
www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 �� www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i][j] : (1,1)에서 (i,j)까지 가는 경로의 수 점화식 if(i+Board[i][j]>N) : DP[i+Board[i][j]][j] = DP[i+Board[i][j]][j] + DP[i][j] if(j+Board[i][j]>N) : DP[i][j+Board[i][j]] = DP[i][j+Board[i][j]] + DP[i][j] #inclu..
www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net [풀이] DP를 이용하여 풀 수 있는 문제였다. DP[i] : i번째 눌렀을 때 A의 최대 개수 점화식 DP[0] ~ DP[5]까지는 A를 하나 출력하는 게 최대 DP[i] = max(DP[i-1]+1,DP[i-3]*2,DP[i-4]*3,DP[i-5]*4) ※화면을 선택하여 복..
www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[x]: 가치의 합 x를 얻기 위해 사용한 동전의 최소 개수 점화식 if coin[i]
www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[x] : 가치의 합이 x가 되는 경우의 수 점화식 if coin[i] k; for (int i = 1; i > coin[i]; } cout
www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net [풀이] 재귀 DP로 풀 수 있는 문제였다. DP[x]: 길이 x인 올바른 괄호 문자열의 개수 #include #include using namespace std; int T, L; long long DP[5001]; long long solution(int len) { //길이가 0이 될 때까지 재귀 돌렸으면 if (len == 0) return 1; long long& res = DP[len]; //이미 ..