Hoon222y

https://www.acmicpc.net/problem/2110 공유기를 c 개 이상 설치하는데 그 간격이 가장 크게 배치하는 방법이다.이 문제의 경우 핵심은 "답을 x라고 가정할 때 그 답이 가능한가?" 라는 질문에 답을하는것이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include#include#include#include#include#include#include#include#include#include using namespace std; int n,c;int main(){ scanf("%d%d" , &n,&c); vector v(n); for(int i=0;i

https://www.acmicpc.net/problem/9466dfs의 사이클을 체크하여 사이클의 경우 dfs를 돌리지 않고 최적화 하는 방법으로 시간을 줄이는 문제이다. 찬란한 오답 퍼레이드 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋdfs상에서 사이클을 체크하는 방법은 아직 끝나지 않았지만 visit된 정점을 방문할경우 사이클이 존재한다고 생각하는 것이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include#include#include#include#include#include#include#include#include#include using namespace std; ..

https://www.acmicpc.net/problem/1300 N*N크기의 배열에서 k번째 수를 구하는 문제이다. N의크기가 10^5까지이기 때문에 배열을 실제로 할당하는것은 메모리 초과 -> 터짐 따라서 다른 방법을 생각해 보아야 한다. 이 문제의 핵심은 parametric search를 이용하는 것이다. 정답이 0과 N*N 사이의 한 정수이기 때문에 이분탐색방식을 이용하여 접근한다. 핵심은 임의의 수를 답이라고 가정하고, 그 수가 k번쨰 수인지 확인하는 방식이다. 여기서 k번째 수라는 뜻은 자기보다 작은 숫자가 k-1개라는 뜻임을 기억하자. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include..

https://www.acmicpc.net/problem/1194 bfs를 이용하여 문제를 해결하는 문제이다. 해당 문제를 풀때 고민해야하는 점이 있다면 어떤점을 이동할때 , 그리고 방문할때 다른 bfs처럼 visit 처리를 해주어야 하는데 그때마다 어떤 열쇠들을 가지고 있는지 그떄의 열쇠상태를 가지고 있어야 한다는 점이다. 하지만 bfs특성상 while문 내에 키의 상태를 가지고 있는 배열 혹슨 백터들을 가지고 실행한다는 것은 메모리 초과로 이어지게 된다.따라서 이러한 경우 필요한 테크닉은 비트마스크를 이용한 처리이다. 문제의 접근 핵심을 정리하자면 (1) 열쇠는 6종류만 가지고 있다. (2) 어떤 지점을 방문할때 visit처리를 위해 visit배열의 선언을 visit[어떠한 열쇠를 가지고 있는지 비트..

https://www.acmicpc.net/problem/14614 XOR연산에 관련된 문제이다. 핵심은 비트연산은 && ,|| 가 아니라 &,|을 쓴다는 것이다.!!!!! 123456789101112131415161718192021222324252627#include #include #include #include #include #include using namespace std; int main(){ int a,b; string c; scanf("%d%d" , &a,&b); cin >>c; int len = c.length(); int ans = ((~a) & b) | (a & (~b)); if((c[len-1]-'0')%2 == 0){ printf("%d\n" , a); }else{ printf(..

https://www.acmicpc.net/problem/1182 n의 범위가 작으므로 그냥 재귀를 통한 완전탐색을 활용한다. 이때 s==0일때는 공집합이므로 예외처리를 해주어야 한다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include #include #include #include #define INF 1e18typedef long long ll;using namespace std; int n,s,arr[44],ans; void solve(int cur , int sum){ if(cur == n+1){ // 해당 범위를 벗어날때 if(sum == s){ ans ++; } return; } so..

https://www.acmicpc.net/problem/1261 벽을 부시면서 원하는 위치에 도달할때까지 최소한으로 벽을 부시는 경우를 구하는 문제이다.2차원 배열 두개를 통하여 움직이고 1개를 깼을 때, 2개 .... 하다가 원하는 위치에 도달할때까지 반복하게 된다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include #include #include #include #include #include #define INF 1e18typedef long long ll; using namespace std; int arr..

https://www.acmicpc.net/problem/14499 음... 이문제는 .. 그냥 시뮬레이션이라서 노가다 구현함 ㅋㅋ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138#include #include ..

https://www.acmicpc.net/problem/13460 정해진 출구까지 이동을 하면서 빨간색 구슬이 파란색 구슬보다 빠르게 나오게 만들어주는 문제이다. 먼저 생각을 해볼것은 "어떠한 방향으로 움직였을때 이동한 결과가 같은 라인에 도착하는가? 아닌가?" 인 듯하다.이동 결과가 같은 라인일 경우에는 동시에 이동하기 때문에 겹치지 않게 처리를 해주는것이 중요하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899..

https://www.acmicpc.net/problem/2206 음 ... 딱봐도 bfs 문제이다. 문제접근을 1) bfs 로 이동 2) 벽을 깨고 이동하는 경우와 아닌 경우를 구분해서 구현이렇게 접근을 하는데 방문했던 지점을 어떻게 처리를 해야할지를 몰라서 해맸다 ... 방법은 3차원 visit배열을 구현하여 벽을 깬적이 없으면 [y][x][1]부분에, 깬적이 있으면 [y][x][2]부분에서 visit처리를 해주었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#includ..