# 출처 : https://www.acmicpc.net/problem/9207 백트래킹을 이용하는 문제인데.. 나중에 다시풀어봐야겠다. # 풀이1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #define endl '\n'using namespace std;int N, pin_cnt, move_cnt;char map[6][10]; const int dR[] = { 1, 0, -1, 0 };const int dC[] = { 0, 1, 0, -1 };bool inRange(int..
# 출처 : https://www.acmicpc.net/problem/15683 dir 이라는 변수로 상,하,좌,우 배열을 모두 확인하는것이나, rotation이라는 배열을 둬서 회전 시킬 최대 크기를 손쉽게 설정하는법 같은 기술들이 많이 녹아들어가 있다. # 풀이1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191..
# 출처 : https://www.acmicpc.net/problem/15686 DFS 와 백트래킹만 적절하게 사용하면 되는 문제인데, 괜히 어렵게 풀다가 오래끌은 문제이다.처음 풀이는 DFS로 depth가 치킨집의 개수 M과 같아지면 BFS로 전체 거리를 조사하는식으로 들어갔는데 시간초과나서 생각해보니..전혀 그럴필요 없이 필요한 거리만 뽑아내면 됐었다. # 풀이12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include #include #define endl '\n';using namespace std;int N,..
#출처 : https://www.acmicpc.net/problem/5014 처음엔 DFS 로 풀다가 메모리초과 떠서 DP까지 생각해 내기 전에 BFS로 다시 풀었다.BFS를 쓸 때 check 배열의 필요성을 못느껴서 dist배열 하나로 끝냈다. #풀이 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #define endl '\n'#define MAX 1000005using namespace std;int F, S, G, U, D;int dist[MAX]; bool inRange(int x){ return x >= 1 && x > D; queue Q; Q.pu..
#출처 : https://www.acmicpc.net/problem/2422 이 문제는 두가지의 풀이를 적어두고 싶다. 첫번째로 나는 chk 배열을 [N의 개수][N의 개수] 크기로 2차원 배열로 잡고 for문을 돌며ans 값을 증가시켜 최종적으로 출력하는 방법을 택했고, 친구는 DFS를 이용해서 풀었다.DFS 를 이용한 풀이에 익숙해지고자 두 풀이 모두 적어두려한다. #풀이(단순 for문 이용)1234567891011121314151617181920212223242526272829303132#include #define endl '\n'using namespace std; int N, M;bool chk[205][205];int main(){ ios::sync_with_stdio(false); cin...
# 출처 : https://www.acmicpc.net/problem/16198 별다른 어려움 없이 재귀와 백트래킹을 이용한 완전탐색을 통해 문제를 풀었다. # 풀이12345678910111213141516171819202122232425262728293031#include #include using namespace std; int N, W[10];bool chk[10];int func(){ int ret = 0; for (int i = 1; i > N; for (int i = 0; i > W[i]; cout
# 출처 : https://www.acmicpc.net/problem/11723 처음 아이디어는 벡터 구현해서 풀면 되겠지 싶었으나 메모리제한을 고려하면 배열을 이용한 벡터는 구현 해도 문제가 될 것 같았다.따라서 비트마스크를 사용하여 풀었다. 기본 연산들 가령 and, or, xor 같은것들을 다시한번 떠올려 볼 수 있었다.이때 remove 에선 and 연산을 사용하여 적절하게 처리할 수 있는데, ~ 를 사용하여 전체 비트를 뒤집고 and 연산을 수행하여원하는 숫자에 해당하는 비트만 제거할 수 있었다. # 풀이1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include ..
# 출처 : https://www.acmicpc.net/problem/14502 BFS를 사용하여 바이러스를 퍼뜨렸고, 재귀를 사용하여 문제에서 요구한 3개의 벽을 세웠다.1. map에 전체 입력을 받음 (이때, 바이러스에 해당하는 2가 들어오면 바로 큐에 넣음)2. 3개의 벽을 세우기 위해 전체를 돌며 0이 보이면 tmp에 map을 카피한 후 재귀로 3개의 벽을 세움.즉, tmp는 최초 map의 모든 0에 벽을 세우기 위한 임시배열.3. 벽을 다 세웠으면 BFS로 들어가서 afterWall이라는 배열에 다시 복사를 한다. 그리고 다시 복사한 이 afterWall 배열을 가지고 바이러스를 퍼뜨린다.4. 매 회 바이러스가 퍼진 이후 0의 개수를 세서 그 최대가 되는 때를 출력. 바이러스가 퍼진 이후 전체를..
# 출처 : https://www.acmicpc.net/problem/6679 처음 내 풀이는 어떤 함수에서 입력으로 들어온 수를 특정 진법으로 변환하고 그 후 리턴하는 함수,리턴받은 수를 자릿수별로 합치는 함수,그리고 최종 결과를 비교하는 함수 총 3가지로 구성하여 풀었으나 풀고보니 풀이가 쓰레기였다.그럴 필요없이 진법 변환의 원리 그러니깐 해당 진법의 수로 나눈 나머지끼리의 합을 이용하면 굳이 string을 쓰거나 하지 않아도 풀 수 있었다.. # 풀이12345678910111213141516171819202122232425#include #include using namespace std; int calc(int num, int base){ int ret = 0; while (num) ret += ..
# 출처 : https://www.acmicpc.net/problem/2193 앞선 2xn 타일링 문제와 마찬가지로 규칙을 찾아 미리 배열 안에 각 N에 해당하는 경우의 수를 담아두고입력받은 N에 대한 값을 꺼내서 출력해주면 된다.여기서 변수 타입을 지정해 주는것이 한가지 독특했던 점이었는데, 처음에 int형으로 풀었더니 틀린것으로 나왔다.디버깅 찍어보니 안에 수들이 깨져있었음(너무 커져서). 따라서 size_t 타입으로 바꿔주고 돌리니 정답으로 나왔다.다른분들의 풀이를 보면 long long을 사용한 분도 있고 다양하더라 # 풀이12345678910111213#include using namespace std;size_t N, cnt[91]; int main(){ ios::sync_with_stdio(..