문제링크 : https://www.acmicpc.net/problem/9658 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int dp[1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; dp[1]=0; dp[2]=1; dp[3]=0; dp[4]=1; //1이 상근이가 이기는 경우 for(int i=5; i 1개 가져가면 상대방이 나머지 가져가야 하므로 이김 dp[..
문제링크 : https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, D; vectorv[10001]; int dist[10001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> D; ..
문제링크 : https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int dp[101][101][101]; string s1, s2, s3; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> s1 >> s2 >> s3; for(int..
문제링크 : https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, S, result; int arr[21]; void dfs(int idx, int sum) { if(idx==N) return; if(sum + arr[idx] ==..
문제링크 : https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, maxV; int arr[1500001][2]; int dp[1500001]; int main() { ios_base::sync_with_stdio(0); cin.tie(..
문제링크 : https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, maxV; int arr[1001]; int dp[1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=0; i> a..
문제링크 : https://www.acmicpc.net/problem/1083 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, S; int arr[51]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=0; i> arr[i]; } cin..
문제링크 : https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; string S, T; int result; void func() { while(1) { if(S==T) { result = 1; break; } else if (S.size(..
문제링크 : https://www.acmicpc.net/problem/14426 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, cnt = 0; vectorv; int main() { ios_base::sync_with_stdio(0); ..
문제링크 : https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int t, n; bool flag; vectorv; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> t; while(t--) ..
문제링크 : https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, sum; vectortree[500001]; bool visited[500001]; void dfs(int n, int cnt) { if(n!=1 && tree[n].size()==1) //리프노트라면..
문제링크 : https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int S; int arr[1001][1001]; //화면, 클립보드 void bfs() { queueq; q.push({1, 0}); //초기화 상태 (화면에 이모티콘 1개) while(!q.empty()) { a..
문제링크 : https://www.acmicpc.net/problem/18116 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M; int parent[1000001]; int cnt[1000001]; int find_root(int x) //부모찾기 { if(x == parent[x]) return x; return parent..
문제링크 : https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M; int parent[1000001]; int find_root(int x) //부모찾기 { if(x == parent[x]) return x; return p..
문제링크 : https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int dp[31]; bool flag = false; int main() { ios_base::sync_with_stdio(0); cin.tie(0); dp[0] = 1, dp[2] = 3; cin >> N; if(N%2) flag = true; //홀수 거르기 for(int i=4; i=0; j-=2) { d..