궤도

문제 풀이 dp로 풀면 더 빠르겠지만 난 그냥 백트래킹으로 풀었다. 3~1을 빼서 음수가 되지 않으면 계속 빼주면서 백트래킹 재귀 함수를 호출한다. 소스코드 #include using namespace std; int cnt; void backtracking(int num) { if (num == 0) { //0이면 카운트 추가 cnt++; return; } for (int i = 3; i >= 1; i--) { //3부터 1까지 뺄 수 있는지 확인 if ((num - i) >= 0) backtracking(num - i); } } int main() { int t, n; cin >> t; for (int i = 0; i > n; backtracking(n)..

문제 풀이 가능한 모양을 하나하나 분리해서 찾는건 이 문제가 브루트포스라고 해도 너무한 방법이다. 보라색 조각을 제외한 나머지 4개의 조각은 백트래킹으로 탐색할 수 있는 조각이다. 백트래킹으로 탐색할 수 있다는걸 쉽게 설명하면 한붓 그리기처럼 탐색할 수 있단 뜻이다. 그럼 보라색 조각을 제외한 나머지 조각은 백트래킹으로 처리한다고 치고, 보라색 조각은 어떻게 처리할까? 이런 조각 하나가 있다고 하자. 이 조각을 기준으로 상하좌우에 조각을 붙이면 이런 + 모양이 될 것이다. 여기에 상하좌우 중 하나의 조각만 빼면 가능한 모든 보라색 조각의 경우가 나올 것이다. 소스코드 링크 = 0) && (nr = 0) && (nc < M)) { //범위에 들어오면 저장 cnt++; arr[i] =..

문제 풀이 홀수인 두 소수의 합으로 짝수를 나타내는 문제이다. 홀수인 두 소수이므로 3부터 시작하면 될 것이고 입력값의 절반까지만 탐색하면 된다. 만약 입력이 8이라면 3+5와 5+3은 같은 말이기 때문이다. 그리고 두 소수의 차가 가장 큰 것을 출력하라고 했는데 그럼 뭐 3부터 탐색하다가 두 소수를 찾으면 바로 출력하면된다. 20은 3+17로도 나타낼 수 있고 7+13으로도 나타낼 수 있지만 두 수의 차가 가장 큰 것은 먼저 발견된 3+17이다. 이 소수를 찾는 과정에서 시간초과가 나지 않도록 빠르게 구하는 것이 중요하다. 나는 에라토스테네스의 체를 사용했다. myunji.tistory.com/61 [백준] 1929번 : 소수 구하기 문제 풀이 에라토스테네스의 체를 이용해 소수를 구하는 문제다. 에라토..

문제 풀이 예제 입력1을 오름차순 정렬해보자 -10 -9 2 4 4 여기서 중복을 제거하면 -10 -9 2 4 이 배열의 인덱스는 당연히 왼쪽에서부터 0, 1, 2, 3이다. 그리고 이건 각 숫자에 대해 해당 숫자보다 작은 수의 개수가 된다. 소스코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int N; long long input; vector arr, sort_arr; cin >> N; for (int i = 0; i > input; arr.push_back(input); //원래 배열 } sort_arr = arr; sort..

문제 풀이 이 문제는 그냥 구글에 이분그래프라고 검색하고 나온 이미지를 보는 것만으로도 한 절반정도는 풀리는 문제이다. 위키백과 이미지를 가져왔다. 그래프의 정점을 빨간색과 초록색으로 칠한 것을 볼 수 있을 것이다. 이분그래프는 인접한 두 정점을 다른색으로 칠한다고 가정할 때 오직 두가지의 색을 사용해서 모든 정점을 칠할 수 있는 그래프이다. 자료구조때 배웠던가...컴퓨터 알고리즘때 배웠던가...암튼 배웠었다. 아이디어는 간단한 이 문제가 정답 비율 20%대인 이유는 간과하기 쉬운 조건 하나와 메모리 초과 그리고 입력 초기화 떄문 아닐까싶다. 먼저 간과하기 쉬운 조건하나를 말해보도록 하겠다. 바로 모든 정점이 연결됐을거란 보장이 없다는 것이다. 이 그림처럼 다른 정점과 연결되지 않은 정점이 있을 수 있다..

문제 풀이 myunji.tistory.com/284 [백준] 2178번 : 미로 탐색 문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까? 시작점에서 바 myunji.tistory.com 이 문제랑 똑같은 유형인데 그냥 방향이 4개에서 8개가 됐을 뿐이다. 소스코드 #include #include #include #include using namespace std; int matrix[300][300], l; pair dir[8] = {{1, -2}, //나이트가 갈 수 있는 방향 {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -..

문제 풀이 너어무 어려웠다. 골드 4길래 풀만할 줄 알았는데 아니었다. 반례가 너무 많았어서 기억도 안나고 여기서 더 최적화 할 수 있을 것 같은데 더 이상 못하겠다. 솔직히 설명도 잘할 자신이 없다. 먼저 난 처음에 기존에 미로찾기 처럼 input 배열을 갱신하는데 이제 벽을 부쉈는지 아닌지를 기록하면 될 것이라고 생각했다. 하지만 이 문제는 2차원 배열 하나로 간단하게 풀리는 문제가 아니었다. 이런 배열이 있다고 하자. 당시엔 matrix를 갱신할 생각이었어서 벽을 -1로 표현했다. 아직 벽을 부술 수 있는 상태는 파란색, 벽을 더이상 부실 수 없는 상태는 빨간색으로 표현했다. 좀 더 진행했다. 보라색은 벽을 부수고도, 안부수고도 갈 수 있음을 나타냈다. 아무튼 이렇게 벽을 부순 상태에서 갱신된 3,..

문제 풀이 얼핏보면 동적계획법 문제라고 생각할 수도 있다. 하지만 수빈이가 계속 앞으로만 이동하는게 아니라 뒤로도 이동할 수 있어서 bfs로 푸는게 훨씬 쉽다. 현재 지점(X)의 X-1, X+1, 2X가 아직 방문한 적 없는 좌표라면 X까지 오는데 걸린 시간에 1을 더해 갱신하면 된다. myunji.tistory.com/284 [백준] 2178번 : 미로 탐색 문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까? 시작점에서 바 myunji.tistory.com 이 문제에서 상하좌우만 뺀거라고 생각해도 된다. 소스코드 #include #include using namespace std; ..