문제링크 : https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int R, C, result = 0; char board[20][20]; //보드 bool visited[26]; //알파벳 방문 여부 체크 int dx[] = {1, -1, 0, 0}; int dy[] ..
문제링크 : https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[100001]; int arr_sum[100001]; int main() { ios_base::sync_with_stdio(0)..
문제링크 : https://www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T, N; cin >> T..
문제링크 : https://www.acmicpc.net/problem/13900 13900번: 순서쌍의 곱의 합 첫 번째 줄에는 입력 받을 정수의 개수 N(2 ≤ N ≤ 100,000) 두 번째 줄에는 N 개의 정수가 주어진다. 이때 입력 받는 정수들의 범위는 0이상 10,000 이하이다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; ll arr[100001]; ll sum = 0; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; ll result = 0; for(int..
문제링크 : https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[10001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N, M; cin >> N >> M; ..
문제링크 : https://www.acmicpc.net/problem/26090 26090번: 완전한 수열 소수는 $2$ 이상의 양의 정수이면서 자기 자신과 $1$ 이외의 양의 정수로 나누어떨어지지 않는 수이다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[501]; int N; bool func(int n) { for(int i=2; i1; //n이 0, 1, 2, 3인 경우 예외처리 } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=0; i> a..
문제링크 : https://www.acmicpc.net/problem/25972 25972번: 도미노 무너트리기 미야노는 $N$개의 도미노를 가지고 놀고 있다. 각각의 도미노는 1차원 좌표계의 $x$좌표 위에 위치하고 있고 길이를 가진다. $i$번째 도미노의 $x$좌표를 $a_i$, 길이를 $l_i$라 하자. 도미노는 오른쪽 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 N, cnt = 1; //기본값은 1 cin >> N; fo..
문제링크 : https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; vector v[801]; int dist[801]; int N, E, v1, v2, a, b, c; int s_to_v1, s_to_v2, v1_to_v2, v1_to..
문제링크 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, result = 0; int arr[20][20]; int dx[] = {1, 0, 1}; int dy[] = {0, 1, 1}; void dfs(int y, int x, in..
문제링크 : https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int dp[2][3]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N, temp0, temp1, temp2; //N과 메모리 절약을 위해 이전 공간 담을 변수 ci..
문제링크 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[15]; int N, result = 0; bool check(int n) { for(int i=0; i N; func(0); cout (x2, y2) : x1-x2 = y1-y2를 만족한다는 것을 이용 - n과 i..
문제링크 : https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int tree[10001]; void postorder(int s, int e) //후위순회 (left, right, root) { if(s>=e) return; if(s == e-1) //하나씩 출..
문제링크 : https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M; int s, e; vector v[1001]; int dist[1001]; void Dijkstra() { priority_queue pq; //비용이 적은순으로..
문제링크 : https://www.acmicpc.net/problem/14908 14908번: 구두 수선공 최소 보상금을 지불하는 작업 순서를 출력해야 한다. 모든 작업은 입력에서의 번호(1~N)로 표시해야 한다. 모든 정수는 한 줄로 표시해야 하며, 각 작업은 공백 문자로 구분한다. 여러 가지 해답 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; pair arr[10001]; //비용, 순서 bool cmp(pair& a, pair& b) { if(a.first == b.first) return a.second < b.second; else retur..
[백준 27921번] 동전 퍼즐 (C++)
문제링크 : https://www.acmicpc.net/problem/27921 27921번: 동전 퍼즐 첫 번째 줄에 정수 $H_1$, $W_1$이 주어진다. ($1\le H_1,W_1\le 10$) 그다음 줄부터 $H_1$개의 줄에 길이 $W_1$의 문자열이 주어진다. ‘.’은 빈칸, ‘O’는 동전이 있는 칸이다. 현재 동전의 배치를 나타낸 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; char c1[11][11]; char c2[31][31]; int H1, W1, H2, W2; int cnt = 0; int maxV = 0; void func(..