Study hard

www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net [풀이] DP를 이용하여 풀 수 있는 문제였다. DP[i] : i번째 칸까지 가는데에 필요한 에너지 양의 최솟값 점화식 DP[j] = min(DP[j], (j-i)*(j-i)+DP[i]) #include #include //min, fill using namespace std; int N; char street[1001]; int DP[1001]; void solution() { DP[1] = 0; for (int i = 1; i < N; i++) { if (street..

www.acmicpc.net/problem/14238 14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net [풀이] 재귀 DP를 이용하여 풀 수 있는 문제였다. (bool) DP[a][b][c][pp][p] : A가 기록을 a번, B는 b번, C는 c번 했고 전전날 pp가 기록을 했고 전날 p가 기록을 한 경우가 가능한지 #include #include using namespace std; int worker[3];//0:A, 1:B, 2:C 입력받은 횟수 저장 bool DP[51][51][51][3][..

www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀�� www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i][j] : i번째 숫자차례에서 덧셈 혹은 뺄셈한 결과가 j인 경우의 수 점화식 DP[i][j+Num[i]] += DP[i-1][j] DP[i][j-Num[i]] += DP[i-1][j] #include using namespace std; int N; int Num[101]; long long DP[101][21] = { 0, }; void soluti..

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) ※화면을 선택하여 복..