문제링크 :https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int N, M, s, e; int h1, h2, k; vector arr[100001]; bool check[100001]; bool bfs(int m) { queueq; memset(..
문제링크 : https://www.acmicpc.net/problem/11899 11899번: 괄호 끼워넣기첫 번째 줄에 S를 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 출력합니다. 불가능한 경우는 주어지지 않습니다.www.acmicpc.net#include using namespace std;#define ll long long#define MAX 987654321#define pii pair int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); string s; cin >> s; queueq; int cnt = 0; for(int i=0; i큐를 활용하여 풀었다. 처음에 큐에 ..
문제링크 : https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int N; int dp[1001]; dp[1] = dp[3] = dp[4] = 1; //상근이 가져감 dp[2] = 0; cin >> N; for(int i=5; i
문제링크 : https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int H, W, result = 0; cin >> H >> W; int WH[500]; for..
문제링크 : https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int arr[100001]; ll Tree[400001]; //세그먼트 트리 ll init(int start, int end, int node) //트리 만들기 { if(start == end)..
문제링크 : https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair vector arr[1001]; bool check[1001]; int bfs(int start, int end) { queueq; q.push({start, 0}); //시작점과 ..
문제링크 : https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair vector arr[1001]; bool check[1001]; void dfs(int n) { check[n]=true; for(int i=0; i> ..
문제링크 : https://www.acmicpc.net/problem/20925 20925번: 메이플스토리 첫째 줄 사냥터 수 $N$ ($1 \le N \le 200$)과 방학 기간을 분 단위로 나타낸 $T$ ($1 \le T \le 1\,000$)가 주어진다. 다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int N, T, result = 0; int c[200], e[200]; int t[200][200]; int dp[2000][1000]; int main(v..
문제링크 : https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int N, M; int arr[7]; int visited[7]; void Backtracking(int n) { if(n == M) { for(int i = 0; i arr[0], a[0] 출력 맨처음 백트래킹을 ..
문제링크 : https://www.acmicpc.net/problem/4883 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int N; int graph[100000][3]; int dp[100000][3]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int T ..
문제링크 : https://www.acmicpc.net/problem/2824 2824번: 최대공약수 첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M(1 ≤ M ≤ 1000)이 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int N, M; ll a[1000]; ll b[1000]; ll res..
문제링크 : https://www.acmicpc.net/problem/1438 1438번: 가장 작은 직사각형 예제 1의 경우 (9,4), (9,6), (14,4), (14,6)을 꼭짓점으로 하는 직사각형을 만들면 된다. www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair bool compare(const pii &a, const pii &b) { return a.second < b.second; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int N, result = MAX; pii p[100];..
문제링크 : https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int N, M, T; int dx[] = {1, -1, 0, 0}; int dy[] = {0 ,0, 1, -1}; int arr[100][100]; int cnt[100][100]; int check[100]..
문제링크 : https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; map m; for(int..
문제링크 : https://www.acmicpc.net/problem/10836 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 www.acmicpc.net #include using namespace std; #define ll long long #define MAX 987654321 #define pii pair int arr[1401]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int M, N; cin >> M >> N; fill(arr,..