문제링크 : 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(..
문제링크 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, K; vector dist(100001, MAX); void Dijkstra() { queueq; q.push(N); dist[N] = 0; while(!q.emp..
문제링크 : https://www.acmicpc.net/problem/25328 25328번: 문자열 집합 조합하기 알파벳 소문자로 구성된 문자열 X, Y, Z가 주어진다. 각각의 문자열에는 중복된 문자가 존재하지 않는다. 문자열 S에 있는 문자 중 임의로 k개를 선택하여 문자열 S에서의 순서를 유지하여 만든 모 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; string x, y, z; int K; map m; void backtracking(int idx, string str, string tmp) { if(tmp.size() == K) { m[tm..
문제링크 : https://www.acmicpc.net/problem/14943 14943번: 벼룩 시장 벼룩시장에서 사람들이 벼룩을 사고 판다. 놀랍게도 각 사람들이 사려고 하는 벼룩의 합과 파는 벼룩의 합은 같다. 벼룩을 사거나 파는 사람들은 서로 일렬로 길게 서 있으며, 인접한 가게 사이 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; ll arr[100001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll N; cin >> N; ll sum = 0; ll result = 0; for(in..
문제링크 : https://www.acmicpc.net/problem/27515 27515번: 1차원 2048과 쿼리 $Q$개의 쿼리에 대해 각각 한 줄에 문제의 정답을 출력하세요. $a$가 빈 수열인 경우 문제의 정답은 $0$으로 간주합니다. 모든 쿼리에 대해 문제의 정답이 $2^{62}$보다 크지 않음이 보장됩니다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; ll arr[64]; //0~63 ll func(ll n) //지수 구하기 { ll cnt = 0; while(n > 0) //2로 나눠가면서 카운트 { n /=2; cnt++; } ret..
문제링크 : https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; if(N==1 || N==3) cout
문제링크 : https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; ll dp[67]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; dp[0] = dp[1] = 1; //초기값..
문제링크 : https://www.acmicpc.net/problem/21870 21870번: 시철이가 사랑한 GCD 첫째 줄에 정수 $N$이 주어진다. ($1 \leq N \leq 200\,000$) 둘째 줄에 자취방의 매물번호를 의미하는 정수 $a_1, a_2, \cdots, a_N$이 주어진다. ($1 \leq a_i \leq 200\,000$) www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int arr[200001]; int gcd(int x, int y) //최대 공약수 구하기 { return (y==0 ? x : gcd(y, ..
문제링크 : https://www.acmicpc.net/problem/13700 13700번: 완전 범죄 첫째 줄에 N, S, D, F, B, K가 주어지고, K > 0인 경우에는 둘째 줄에 경찰서의 위치 l1, l2, …, lK가 주어진다. (1 ≤ S, D ≤ N ≤ 100000, 0 ≤ F, B ≤ 100000, 0 ≤ K ≤ N/2, S ≠ D ≠ l) www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, S, D, F, B, K; //건물, 금은방, 집, 앞으로, 뒤로, 경찰서 int arr[100001]; //경찰서 int visite..
문제링크 : https://www.acmicpc.net/problem/15966 15966번: 군계일학 첫째 줄에 수열의 길이 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에, ai (1 ≤ i ≤ N, 1 ≤ ai ≤ 1,000,000)이 주어진다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[100001]; int dp[1000001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N, result = 0; cin >> N; for(int i=1; i> arr[i..
문제링크 : https://www.acmicpc.net/problem/19699 19699번: 소-난다! 지난 번 헛간 청약의 당첨우(牛)가 발표됐다. 청약에 당첨된 소들은 날아갈 듯이 기뻐하다가 진짜로 하늘을 날았다. 하지만 이후로 소들은 날 수 없었다. 그러던 어느 날, 꿀벌에게 쏘이면 잠깐 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int arr[9]; bool check[9000]; sets; int N, M; void func(int cnt, int idx, int sum) { if(cnt == M) //선별할 숫자와 같으면 { if(ch..
문제링크 : https://www.acmicpc.net/problem/12993 12993번: 이동3 첫째 줄에 x와 y가 주어진다. (0 ≤ x, y ≤ 1,000,000,000) www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int x, y; cin >> x >> y; bool flag = 0; if(x==0 && y==0) flag = 1; //예외처리 int mutiple = 1; int i; //곱해진 횟수 for(i=1; i max(x,y)) ..