youtu.be/Q6pa2akgUGI [섬의 개수 정답 코드] #include #include using namespace std; int field[51][51]; int visited[51][51]; //팔방 check int dx[] = { 0,0,-1,1,-1,1,-1,1}; int dy[] = { -1,1,0,0,-1,1,1,-1 }; int n, m; queue q; void bfs(int x, int y,int cnt); int main() { ios_base::sync_with_stdio(0); cin.tie(0); while (1) { int cnt = 1; cin >> n >> m; if (n == 0 && m == 0) return 0; for (int i = 0; i < m; i++..
Koala - 2기/C반
[문제 풀이] 영상 참고. www.youtube.com/watch?v=I0Dq42C0h8w&feature=youtu.be&ab_channel=%EC%B2%9C%EC%88%98%ED%99%98 [코드] #include #include using namespace std; int n, m, ans = 0; int field[8][8]; int clone_field[8][8]; int dx[] = { 0,0,-1,1 }; int dy[] = { -1,1,0,0 }; //바이러스를 퍼트림. void bfs(); //a field에 b field를 복사함. void clone_it(int(*a)[8], int(*b)[8]); //세개의 벽을 세움. void make_wall(int cnt); int main() ..
[문제 풀이] 영상 참고 www.youtube.com/watch?v=I0Dq42C0h8w&feature=youtu.be&ab_channel=%EC%B2%9C%EC%88%98%ED%99%98 [코드] #include #include #include #include using namespace std; int dx[] = { -1,1,0,0 }; int dy[] = { 0,0,-1,1 }; int field[101][101] = { 0, }; int visited[101][101] = { 0, }; int* alti; int n,cnt; queue q; void bfs(int alt, int cnt); int main() { int ans = -1; cin >> n; vector alti; for (int ..
[문제 풀이] 영상 참고 www.youtube.com/watch?v=I0Dq42C0h8w&feature=youtu.be&ab_channel=%EC%B2%9C%EC%88%98%ED%99%98 [코드] #include #include #include #include #include #include using namespace std; int n, m, v; vector a[1001]; bool visited[1001] = { 0, }; stack s; void dfs(int v); void bfs(int v); int main() { ios_base::sync_with_stdio(0); int ltemp, rtemp; cin >> n >> m >> v; while (m--) { cin >> ltemp >> ..
2346번: 풍선 터뜨리기 첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자. www.acmicpc.net 큐, 덱으로는 돌아가는 식의 문제를 내는 것이 국룰인것 같습니다. 이 문제도 반전 요세푸스와 풀이 과정은 비슷하나, 첫 입력 인덱스를 기억해야 한다는 것이 까다롭습니다. 그래서 pair로 덱에 입력을 받겠습니다. 비교할 때는 first를 통해 비교하고, 출력할 때는 second를 출력할 것입니다. [정답코드 보기] #include #include #include #include #include #include #include #include #include using namespace std..
풀이 더보기 x의 범위가 크기 때문에 1씩 증가시키는 방법으로 풀면 시간초과가 나게 된다. 따라서 이분 탐색을 통해 풀어야 한다. 이 때, 99% 승률에서는 100%가 될 수 없다는 점을 유의하여 예외로 처리해주어야 한다. 소스 코드 더보기 #include using namespace std; long long x, y, z; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> x >> y; z = (y * 100) / x; //바뀌지 않는 경우 if(z >= 99){ cout
풀이 1 더보기 가로등의 위치는 정해져있고 0부터 N까지의 돌다리를 밝혀야 한다. 가로등은 가로등의 위치(pos)에서 가로등의 높이(h)만큼 양 옆으로 밝힐 수 있다. 높이가 높아질수록 비용이 많이 든다 최소 비용을 위해 가로등 높이는 최소가 되어야한다. 1. 가로등의 높이를 x라고 가정하고 생각했을 때 h가 x인 상황에서 돌다리를 전부 밝힐 수 있는지 없는지를 판별할 수 있다. 2. 가로등의 높이가 x일때 돌다리가 전부 밝혀진다면 x보다 높은 높이는 당연히 모든 돌다리를 밝힐 수 있다. 위의 두가지 조건에 의해서 Parametric Search를 이용할 수 있다. 가로등 높이가 될 수 있는 범위(left~right)내에서 이분탐색의 아이디어를 이용하여 특정 높이를 정하고(mid = (left+right..
※docs.microsoft.com/ko-kr/cpp/standard-library/set?view=msvc-160docs.microsoft.com/ko-kr/cpp/standard-library/unordered-set?view=msvc-160 에서 더욱 자세히 살펴보실 수 있습니다. 해시를 매우면서 살펴본 map은 다음과 같은 강점이 있었습니다. 해시는 요소를 저장할 때 키값을 중점으로 레드-블랙 트리로 저장하기 때문에, 레드블랙 트리의 특징을 그대로 가져갑니다. 하지만 정렬과 연산을 매우 많이 해야 할 때는 O(nlogn)의 시간 자체가 부담스러울 수 있습니다. 그래서 우리는 unordered_set을 사용합니다. 이 클래스는 요소를 정렬하여 저장하지 않습니다. 또, 그 자체를 해시로 저장합니다. ..
풀이 더보기 큐를 활용한 간단한 문제이다. 3분 30초는 210초이고 210초에서 흐르는 시간을 까든, 0초부터 시작해서 210초를 초과하는 조건을 걸든 210초 시간 제한을 둔다. 1. 8명을 que에 넣고 시작하는 사람의 번호가 첫번째 que.front()에 오게 둔다. 2. if(사람이 T를 받으면) { 시간을 깎고 다음 사람한테 폭탄을 준다. } else{ N이나 P를 받았으면, 시간만 까고 그 사람에게 폭탄을 유지한다. } 3. 위 조건에서 210초가 지나면 그 당시에 폭탄을 들고 있었던 사람을 출력한다. (풀이는 내가 짠 코드와 리더님이 짜주신 코드 두 개 동봉합니다.) 소스코드1 더보기 int main(){ int n, t, z; int time_ticking = 0; cin>> n; whi..
문제 풀이 더보기 단순한 버블정렬이고, 한번 정렬을 시행할 때마다, 출력해주면 된다. 아주 기본적인 것이지만, 배열에 쓰레기값 여부를 고려해야, "초과 출력"같은 오류에서 허우적대지 않는다.. 소스 코드 더보기 // // main.cpp // b_2949 // // Created by 이동연 on 2021/01/25. // #include using namespace std; int main(){ int ary[6] = {0}; ary[5] = 10; for(int i = 0 ; i > ary[i]; } for(int i = 0 ; i ary[j+1]){ int temp = 0; ..
www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 이 문제 진짜 어렵더라구요... 저도 해설 보고 풀었습니다. 근데 해설들이 하나같이 참 대충이더라구요... DP의 길은 참 멀고도 먼 것 같습니다. [정답 코드 보기] 더보기 #include #include #include #include #include #include using namespace std; int main() { int n; int field[1500] = { 0, }; int dp..
www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 고생 많으셨어요! DP문제들을 너무 잘 풀어주셔서 살짝 어려운 문제들을 내봤습니다. 근데 너무 어려웠던 것 같아요.... 저도 다시 푸려니까 어렵더라구요... 죄송합니다... 그럼 풀이 바로 시작하겠습니다! [정답 코드 보기] 더보기 #include #include #define mod 1000000; using namespace std; int main() { ios_base::sync_with_stdio(0); string ..
