문제링크 : https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[1001]; int dp[1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; for(int i=1; i> arr[i]..
문제링크 : https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; vectorv; vectorp; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; v.resize(N+1); for (int i = 2; i*i
문제링크 : https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int result[2501]; int dp[2501][2501]; string s; int main() { ios_base::sync_with_..
문제링크 : https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; struct p { string name; int korean, english, math; }; vectorv; bool cmp(p a, p b) { if(a.korean==b.korean &..
문제링크 : https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; vector v; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T, N; cin >> T; while(T--) { cin >> N;..
문제링크 : https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; string s1, s2, result; int dp[1001][1001]; int main() { ios_base::sync_with_stdio(0); cin.ti..
문제링크 : https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, result = 0; int parent[500001]; int find_root(int x) { if(x == parent[x]) return x; //루트노드면 그대로 반환 return ..
문제링크 : https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; vectorv; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> N; v.resize(N); for(int ..
문제링크 : https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[9][9]; vectorv; bool check(int y, int x, int n) { for(int i=0; i
문제링크 : https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[9][9]; bool row[9][9], col[9][9], square[9][9]; void func(int cnt) { int y = cnt/9; int x = cnt%9; if(cnt==8..
문제링크 : https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, result = MAX; int arr[1001][3]; int dp[1001][3]; int main() { ios_base::sync_with_stdio(false); ..
문제링크 : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; struct p { int u, v, weight; bool operator> N >> M; for(int i=0; i> a >> b >> c; v.push_back({a, b..
문제링크 : https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[1001]; int dp[1001]; int len = 0; vectorv; int main() { ios_base:..
문제링크 : https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; bool check(string tmp) //펠린드롬인지 아닌지 확인 { for(int i=0; i> s; for(int i=0; i
문제링크 : https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; ll N, P, Q; map m; //시간초과 방지 ll func(ll n) { if(n==0) return 1; if(m[n]) return m[n]; //map에 값이 있으면 바로 return (중복방지) return m[n] = func(n/P) + func(n/Q); } int main() { ios_base::sync_with_stdio(0); c..