[BOJ 10453] 문자열 변환

- 문제 요약 1. ab는 좋은 문자열이다. 2. 만약 문자열 [S]가 좋은 문자열이라면, 오른쪽과 왼쪽 끝에 각각 a와 b를 추가한 문자열 a[S]b 또한 좋은 문자열이다. 3. 만약 문자열 [S]와 [T]가 좋은 문자열이라면 이들을 붙여 쓴 [S][T] 또한 좋은 문자열이다. 첫 줄에 테스트 케이스의 수 T가 주어진다. 각각의 테스트 케이스마다, 한 줄에 문자열 A, B가 공백으로 분리되어 주어진다. (2문자열 A를 '인접한 두 문자를 서로 바꾸는' 연산을 통해 문자열 B로 바꾸려고 한다. 이때 필요한 연산의 최소 횟수를 구하는 프로그램을 작성하시오. A를 B로 바꾸는 중에 나타나는 문자열도 모두 좋은 문자열이어야 한다.  - 알고리즘 정리 문자열 A에서 인접한 두 문자를 서로 바꾸는 연산을 통해 문..

[BOJ 4563] 리벤지 오브 피타고라스

- 문제 요약 A^2 + B^2 = C^2피타고라스 정리에서 A(2A)의 개수를 구하시오.(입력은 여러 개의 테스트케이스로 이루어져 있으며, 입력의 마지막 줄에는 0이 하나 주어진다.)  - 알고리즘 정리 피타고라스 정리 수식을 변형해서 문제를 해결할 수 있습니다. A^2 + B^2 = C^2A^2 = C^2 - B^2 = (C+B)(C-B) = x * y(A^2의 약수에서 조건 설정 후 걸러내기)  - 코드 작성 #includeusing namespace std;typedef long long ll;int result;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); while(true){ ll a; cin>>a..

[BOJ 2631] 줄 세우기

- 문제 요약 N명의 아이들이 임의의 순서로 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.  - 알고리즘 정리 옮겨지는 아이의 수를 최소로 하기 위해서는 현재 서 있는 줄에서 LIS를 찾고, 전체 어린이 수에서 LIS의 길이를 빼주면 됩니다.  - 코드 작성 #includeusing namespace std;#define MAX 201int n,arr[MAX],dp[MAX],mx;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i=0;i>arr[i]; } for(int i=0;iarr[j] && dp[i]

[BOJ 14728] 벼락치기

- 문제 요약 첫째 줄에는 이번 시험의 단원 개수 N(1(단, 여러 단원을 융합한 문제는 출제하지 않는다. 한 단원에 한 문제를 출제하며, 어떤 단원의 문제를 맞추기 위해서는 그 단원의 예상 공부 시간만큼, 혹은 그보다 더 많이 공부해야만 맞출 수 있다.)  - 알고리즘 정리 냅색 문제입니다. dp[x] = max(dp[x], dp[x-(예상 공부 시간)] + (문제 배점의 최대값))위 점화식을 사용하여 해결할 수 있습니다.  - 코드 작성 #includeusing namespace std;#define MAX 10001int n,t,dp[MAX],arr[101][2];int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);..

[BOJ 9084] 동전

- 문제 요약 동전의 종류가 주어질 때, 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.입력의 첫 줄에는 테스트케이스의 수 T가 주어진다.각 테스트케이스의 첫 번째 줄에는 동전의 가지 수 N(1(같은 동전이 여러 번 주어지는 경우는 없다. 방법의 수는 2^31-1보다 작다.)  - 알고리즘 정리 DP[i] (i원을 만들 수 있는 방법의 수)DP[i] = DP[i] + DP[i - (동전의 금액)]  - 코드 작성 #includeusing namespace std;#define MAX 10001typedef long long ll;int t,n,m,arr[21],dp[MAX];int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout..

[BOJ 15989] 1, 2, 3 더하기 4

- 문제 요약 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.합을 나타낼 때는 수를 1개 이상 사용해야 하며, 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.(테스트케이스의 수 T가 주어진다. n은 양수이며 10,000보다 작거나 같다.)  - 알고리즘 정리 DP 문제입니다. DP[X][a] (정수 X를 만들 때 a로 끝나는 경우의 수) DP[i][1] = DP[i-1][1] DP[i][2] = DP[i-2][1] + DP[i-2][2] DP[i][3] = DP[i-3][1] + DP[i-3][2] + DP[i-3][3]  - 코드 작성 #includeusing namespace std;#define MAX 10001int t,n,dp..