목록PS/알고리즘 문제풀이 (157)
득이공간
5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net #include using namespace std; int Tree[10001]; void DFS(int Current, int End) { if (Current > End) { return; } int Mid = End + 1; for (int i = Current + 1; i Tree[Current]) { Mid = i; break; } } DFS(Current + 1, Mid - 1); DFS(Mid, End); cout Tree[i]; if..
2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net #include using namespace std; int Max[2][3]; int Min[2][3]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; int A, B, C; cin >> A >> B >> C; Max[0][0] = A; Max[0][1] = B; Max[0][2] = C; Min[0][0] = A; Min[0][1] = B; Min[..
4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net #include #include #include #include #include using namespace std; typedef pair star; typedef tuple edge; vector Stars; vector EdgeList; int Root[100]; float MakeDistance(const star& A, const star& B) { float AX = A.first, AY = A.second; float BX = B.first, BY =..
2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net #include #include #include using namespace std; list Neighbors[1001]; int Entries[1001]; bool Visited[1001]; queue SQ; int Solution[1000]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N, M; cin >> N >> M; for (i..
2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net #include #include using namespace std; const int Infinite = INT_MAX; const int MoveCost[5][5] = { { 0, 2, 2, 2, 2 }, { 0, 1, 3, 4, 3 }, { 0, 3, 1, 3, 4 }, { 0, 4, 3, 1, 3 }, { 0, 3, 4, 3, 1 } }; int DP[100000][5][5]; void Init() { for (int i..
2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net #include #include #include using namespace std; int A[1001]; int B[1001]; vector ASum; vector BSum; void Init() { int N, M; cin >> N; for (int i = 0; i > A[i]; } cin >> M; for (int i = 0; i < M; ++i..
1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net #include #include using namespace std; bool Prime[4000001]; vector Sequence; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; for (int i = 2; i
20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net #include using namespace std; int Root[500000]; int Find(int Node) { if (Node == Root[Node]) { return Node; } return Root[Node] = Find(Root[Node]); } bool Cycle(int NodeA, int NodeB) { int RootA = Find(NodeA); int RootB = Find(NodeB); if (RootA == RootB) { r..
10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net #include using namespace std; int Num[2000]; bool DP[2000][2000]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; for (int i = 0; i > Num[i]; } for (int i = 0; i < N; ++i) { DP[i][i] = true; if (i < N - 1) { DP[i][i + ..
9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net #include #include using namespace std; int DP[1001][1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string A, B; cin >> A >> B; int N = A.size(); int M = B.size(); for (int i = 1; i 0) { if (DP[i][j] =..