문제링크 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int dp[100001][3]; const int MOD = 9901; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; dp[1][0] = 1; //ox dp[1][1] = 1; //xo dp[1][2] = 1; //xx for(int i=2; i OX or XX 가..
문제링크 : https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, result=0; int arr[201]; int dp[201]; // LIS 이용 int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(..
문제링크 : https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M; int arr[1001][1001]; int result = 0; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> M; for(int i=1; i> s; for(int j=1; j 좌 : 1, 좌..
문제링크 : https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int arr[101]; ll dp [101][21]; //i번째 숫자까지의 조합으로 j를 만드는 경우 int main() { ios_base::sync_with_stdio(0); cin.tie..
문제링크 : https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; string s; const int MOD = 1000000; int dp[5001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> s; dp[0]=dp[1]=1; ..
문제링크 : https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, K; const int MOD = 1000000000; int dp[201][201]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> K; for(int i=0; i
문제링크 : https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, K; int arr[101]; int dp[1000001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >..
문제링크 : https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, result; int dp[1001][10]; const int MOD = 10007; int main() { ios_base::sync_with_stdio(0); ..
문제링크 : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[101]; int dp[10001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N, K; cin >> N >> K; for(int i=0..
문제링크 : https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; vectorv; int dp[100001]; int result = MAX; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int C, N; cin >> C ..
문제링크 : https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, result; int arr[100001]; int visited[100001]; void func(int idx) { int cur = idx; while(1) { visited[cur]=idx; cur ..
문제링크 : https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int dp[100001][5][5]; vectorv; int move(int a, int b) { if(a==b) return 1; //똑같은 위치로 이동 else if(a==0..
문제링크 : https://www.acmicpc.net/problem/15235 15235번: Olympiad Pizza The contestants that get a slice are, in order: 1, 2, 3, 4, 2, 4, 2, 4, 4. So at t=1s the first contestant get all slices, at t=3s the third contestant gets a slice, at t=7s the second student finishes and finally at t=9s the fourth student gets the last s www.acmicpc.net #include using namespace std; typedef long long ll; typed..
문제링크 : https://www.acmicpc.net/problem/1788 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; const int MOD = 1000000000; int dp[1000001]; int sign=1; int main() { ios_base::sync_with_stdio(0); ci..
문제링크 : https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; const int MOD = 1000000009; ll dp[1000001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; dp[1] = 1; dp[2] = 2; dp[3] = 4;..