jmmm_25

이 문제의 예제에서는 영역이 3가지로 구분이 될 수 있다. 그래서 나는 DFS를 통해 세 영역을 구분해주었다.첫 번째 영역을 1, 두번째 영역을 2, 세번째 영역을 3 이렇게 구분해준 뒤, BFS를 통해 각 영역간의 최소 거리를 구했다.이렇게 푸는 것이 가장 단순한 방법은 아니지만, 이렇게 밖에 생각이 안났다. 결국 DFS, BFS 두 알고리즘을 모두 알아야 풀 수 있는 문제이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#inc..

전형적인 완전 탐색 문제이다.상근, 창영, 현진의 찍은 답을 정답과 비교해서 맞은 갯수를 처리하여 출력하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include #include #include using namespace std; string Adrian, Bruno, Goran;char answer[101];int cnt[3];vector result;int N; bool compare(const pair &a, const pair &..

start : 1033, finish : 8179 라고 하면, start를 큐에 넣고 BFS 탐색을 이용해 풀면 된다.8179가 pop될 때의 ret를 출력시키면 되는 문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100#include #include #include #include using namespace std; class Info {public: int data, ret; Info() {}; Inf..

dfs 알고리즘으로 풀면 되는 문제인데, 처음에 어떻게 접근해야할지 감이 안잡혔다.그런데 문제 유형이 2638번 치즈 문제와 비슷한 문제였다. 2638번 치즈 : https://www.acmicpc.net/problem/2638 다행히, 치즈 문제를 풀었어서 그때의 기억으로 문제를 풀었다.다른 점이 있다면, 치즈는 0이 아닌 수로 둘러 쌓인 0 근처의 값들을 감소시키지 않는데, 이 문제는 이것까지 고려해야 한다. 이중 for문으로 전체를 돌리면 간단하게 해결되는 문제이다. 소스는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364..

문제만 읽었을 경우에 처음에 이해가 안돼서 계속 고민하다가 찾아본 문제이다.그냥 단순히 DFS 탐색을 해서 정해진 n만큼 동 서 남 북으로 이동할 때 확률을 구하는 문제이다. 중요한 문제인지는 모르겠다.n

이분 그래프를 이산 수학을 배울 때 공부를 했었는데, 금방 잊어버려서 다시 공부를 했다. 이 문제를 풀 때 반례가 있다. BFS로 문제를 풀었는데, 그래프가 연결되어 있지 않고 연결 요소가 2개 이상일 수도 있어서모든 vertex를 다 탐색하며 ret 값을 바꿔줘야 한다. 이 간단한 것을 생각 못해서 처음에 계속 틀렸다. 그리고, 2차원 vector인 adj를 초기화하는 과정에서 adj.resize()를 하면 초기화가 되는 것인지 알았는데, 그렇지 않아서 adj.clear()를 먼저 해주고 해야한다.오랜만에 BFS 문제를 풀어서 그런지 약간 헷갈려서 좀 많이 틀렸던 문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404..

1019번 책 페이지의 문제는 입력이 10억이다. 따라서 1억이 1초 이기 때문에, 당연하게 O(n)으로 코드를 작성할 경우 시간초과가 뜰 것이다.그래서 다른 방식으로 접근을 해야한다. 이 문제를 처음 풀었을 때에는 우선 int형 배열 answer[10] 을 만들고, for문으로 1 ~ N ( 10억 ) 까지 돌리면서 각 자릿수의 숫자인 answer[각 자리의 숫자 값]++ 를 해주면서코딩을 하려고 했다. 그러나, 아무리봐도 이는 시간초과가 날 것임이 당연했고 결국 틀렸다. 그래서 다른 방식으로 접근하려 했는데, 생각이 나지 않아 백준의 문제 풀이를 참고했다. 문제의 시작을 바꿔본다. 예를 들어, 책의 시작 페이지가 17쪽이고, 마지막 페이지는 53쪽 이라고 가정하자. start = 17finish = ..

int pos, cnt를 가진 클래스 Info를 만들어주고 BFS 탐색을 하면 된다. 예제 : 10 1 10 2 1 의 경우 건물의 MAX 높이는 10이고, 시작은 1층, 도착해야할 위치는 10층이다.이 경우에는 U U U U U D 이처럼 6번을 누르면 가장 적게 누른 버튼 횟수이다. BFS 탐색을 할 때, isVisited 배열을 만들어 준 후, 그 층에 방문할 수 있다면 true로 저장을 시킨다.탐색 중에 pos와 g가 같은 경우 cnt를 출력시켜 주고, 만약 탐색이 끝났는데 그 층수에 도착하지 못하였다면 58 줄에서 isVisited[g]의 값이 false 이므로, "use the stairs" 를 출력시키고 종료 시키면 된다. 마지막으로, s와 g의 값이 처음부터 같을 경우에는 0을 출력시키면 ..

보물섬 문제는 인접 행렬로 상하좌우를 확인하며 BFS 알고리즘을 사용하면 된다.이중 for문을 이용해서 'L' 일경우에만 BFS 탐색을 시작하여 max 값을 찾아내 출력하면 된다. 소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #include #include using namespace std; class Info {public: int x, y, cnt; Info() {}; Info(int _x, int _y, int _cnt): x(_x), y(_y..

1072번 게임 문제의 경우, 입력 X가 10억보다 작거나 같은 수 이므로 시간 초과가 날 가능성이 높다.따라서, for문으로 1 ~ 10억 까지 증가시키기 보다는, 이분 탐색으로 정답을 출력하는 것이 좋다. 소스는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #define MAX_INF 1000000000using namespace std; long long x, y, z; int main(int argc, char const *argv[]) { long long l, r, mid; while(cin >> x >> y) { long long temp_z = 0; z = 100 * y /..