위의 문제는 브루트포스로 풀려고 하면 무조건 시간초과가 뜬다. 마지막 해는 M 과 N 의 LCM 이다. M 과 N 이 소수라면 그 크기는 대략적으로 40000 * 40000 정도가 되니 이는 1초이상의 결과가 나온다. 따라서 다른 방법을 생각해 봐야 한다. 핵심 : 1. 위 문제에서 우리가 구하고자 하는 년도를 k 로 둔다. 2. (k - x) % M == 0, (k - y) % N == 0 이다. (위의 2번의 유도는 아래의 사진을 첨부한다.) 3. k 를 M 만큼 증가시키면 그 나머지는 계속 x 를 유지한다.(k % M == x 일 때 (k + M) % M == x 이다) 위의 3번 방식으로 지속적으로 k 를 M 만큼 증가시키면 LCM(M, N) / M 정도의 big O 를 가지므로 시간제한에 안걸릴..
문제링크 : https://www.acmicpc.net/problem/11286 1. 입력 관련 힙과 관련된 문제였다. 힙을 직접 구현하지 않고 힙의 구조를 가지고 있는 priority queue 를 사용했다. 절대값이 가장 작다는 것은 0과 가장 가깝다는 것이다. 즉 -1 과 3 을 비교 했을 때 -1 이 더 가깝다는 것이다. 즉 가장 0과 가까운 수를 결정할 때 부호는 영향을 주지 않는다. 하지만 출력을 할 때는 부호를 신경써야 하기 떄문에 아래와 같은 pair 를 둔다. pair 소스는 아래와 같다. #include #include using namespace std; int N, inp; priority_queue pq; pair pqTop; int main(void){ ios_base::sync..
문제 링크 : https://www.acmicpc.net/problem/1931 문제 핵심 : 정렬 후 그리디 1. 문제를 처음에 풀 때 들어올 수 있는 최대 크기가 100,000 이었으므로 n^2 으로는 못풀어서 브루트포스는 배제했다. 2. 따라서 n log n 이나 n 으로 풀 수 있는지 확인했다. 3. input case 를 적절하게 정렬을 하면 시간을 충분히 줄일 수 있을 것 같았다. (사실 이것도 긴가민가 했음) 정렬의 기준 : input case 에서 들어오는 start, end 값들을 pair vector 로 표현했다. 문제에서 start 와 end 중에서 end 가 중요하다는 것을 깨달았다. end 를 기준으로 오름차순 정렬을 하게 되면 앞에서부터 차례대로 순회하면서 조건을 만족하면 회의 ..
기본적인 BFS 문제였다. 처음에 BFS 로 구현해서 바로 제출을 했는데 틀렸다. 처음에 depth 라는 변수를 두고 그 while 문 들어가는 곳에 depth ++ 로 BFS 의 깊이를 측정하려 했다. 그렇게 되면 depth 가 증가하기만 하고 q 에서 pop 되는 지점으로 depth 를 돌려야 하는데 그렇게 하지 못했다. 아래 소스는 내가 틀렸던 소스이다. #include #include #include #include #include using namespace std; int M, N, A, B; int friendArr[102][102]; int check[102]; int kbArr[102]; int BFS(int start, int friendNum){ queue q; check[start]..
기본적인 DP 문제였다. 처음에는 1차원 dp 로 생각하려 했다. 그런데 i 번째로 올 수 있는 경우의 수가 많아서 1차원 dp 는 안된다는 걸 알았다. 그래서 0, 1, 2 로 dp 를 나눠서 생각하기로 했다. x == 0 : 0 은 x 번째 계단을 선택하지 않는 것 x == 1 : 1 은 x 번째 계단을 선택하고 x-1 은 선택하지 않는 것 x == 2 : 2 는 x 번째, x-1 번째 계단을 선택하고 x-2 번째 계단은 선택하지 않는 것 https://www.acmicpc.net/problem/2579 #include #include #include #include #include #include #include using namespace std; int dp[3][301]; int stair[3..
백준 10250 핵심로직 왼쪽 아래부터 위로 그 다음 열 제일 아래서 다시 위로가 최소 거리로 넣는 방식이다. N % H 가 0 이면 H 을 넣어야 한다. #include #include using namespace std; int T, H, W, N, result; int tmpArr[2]; int main() { cin >> T; for (int i = 0; i > H >> W >> N; if (N % H == 0) { result = H * 100 + N / H; } else { result = N % H * 100 + N / H + 1; } cout
백준 4153 핵심로직 피타고라스의 정리 이용 입력이 작은 순으로 들어오는 게 아니기 때문에 sorting 필요 #include #include using namespace std; int triArr[3]; int main() { for (int i = 0; ; i++) { cin >> triArr[0] >> triArr[1] >> triArr[2]; if (triArr[0] == 0 && triArr[1] == 0 && triArr[2] == 0) break; else { sort(triArr, triArr + 3); if (triArr[0] * triArr[0] + triArr[1] * triArr[1] == triArr[2] * triArr[2]) cout
백준 1805번 직사각형에서 탈출 핵심로직 좌표평면을 생각하면 편하다. 4 가지 중 최소값을 가져오면 된다. -> x 와 w 사이의 거리, y 와 h 사이의 거리, x 와 y축 사이의 거리, y 와 x 축 사이의 거리 #include #include using namespace std; int x, y, w, h, result; int main() { cin >> x >> y >> w >> h; result = min({x, y, h-y, w-x}); cout
