[Programmers] #120802 - 두 수의 합 구하기 [Java][C++][Python]
문제 링크 1. 아이디어 정수 num1, num2가 주어질 때, 두 수의 합을 반환하면 되는 간단한 문제다. 2. 복잡도 접근 시간 공간 풀이 $O(1)$ $O(1)$ 3. 코드 풀이 [Java][C++]...
문제 링크 1. 아이디어 정수 num1, num2가 주어질 때, 두 수의 합을 반환하면 되는 간단한 문제다. 2. 복잡도 접근 시간 공간 풀이 $O(1)$ $O(1)$ 3. 코드 풀이 [Java][C++]...
문제 링크 1. 아이디어 문제의 설명이 난해한데 $O(n)$에 대해 구하므로 $g(n) = n$으로 두면 간단하게 $f(n) = a_1 \times n + a_0 \le c \times n$을 $n \ge n_0$인 모든 $n$에 대해서 만족하는지 판단하는 문제다. 해당 조건을 만족하려면 $n \ge n_0$인 $n$에 대해 $(a_1 - c...
문제 링크 1. 아이디어 양방향 간선들이 주어진 그래프에 대해 너비 우선 탐색을 하면 되는 문제로 인접 리스트를 활용하면 되며, 오름차순 방문을 위해 정렬을 한 번 했다. 방문의 경우 시작점에서의 거리도 구해야 하므로 거리 배열을 활용해서 거리도 기록을 했고, 이후 한번 쭉 순회하며 방문 순서와 거리의 곱을 계산했다. 합을 계산하는 과정에서 ...
문제 링크 1. 아이디어 BaekJoon 9657번 - 돌 게임 3 문제에서 $N$이 최대 $10^{12}$까지 커진 문제로, 이전처럼 dp 표를 채울 수 없으니 승패의 반복 규칙을 찾아야 한다. 돌이 0개인 상태를 지는 자리(L)로 두고 이전 문제의 점화식으로 차례로 구하면 승패가 L, W, L, W, W, W, W 순서로 나오고, 인덱스 ...
문제 링크 1. 아이디어 BaekJoon 9655번 - 돌 게임 문제에서 $N$이 최대 $10^{12}$까지 커진 문제로, dp 표를 채울 수 없으니 홀짝 규칙을 이용해야 한다. 1개와 3개가 모두 홀수라서 한 번 가져갈 때마다 남은 돌의 홀짝이 바뀌므로, 처음 돌이 홀수 개이면 상근이는 매번 짝수 개를 넘기며 마지막 돌을 가져가고 창영이는 ...
문제 링크 1. 아이디어 돌 게임 3과 같은 규칙에서 마지막 돌을 가져가는 사람이 지는 문제다. 돌이 i개 남은 차례의 사람이 이기면 true인 dp[i]를 두면 점화식은 dp[i - 1], dp[i - 3], dp[i - 4] 중 false가 하나라도 있으면 true라는 점에서 돌 게임 3과 같고, 달라지는 것은 초기값뿐이다. 돌이 1개 남...
문제 링크 1. 아이디어 1개, 3개 또는 4개씩 돌을 가져가며 마지막 돌을 가져가는 사람이 이기는 게임에서 두 사람이 최선을 다했을 때의 승자를 구하는 문제다. 두 사람이 최선을 다하면 돌이 i개 남은 상태는 그 차례의 사람이 이기는 상태와 지는 상태 둘 중 하나로 정해지므로, 이기면 true인 dp[i]를 정의할 수 있다. 1개, 3개, ...
문제 링크 1. 아이디어 돌 게임과 규칙은 같지만 이번에는 마지막 돌을 가져가는 사람이 지는 문제다. 1과 3이 모두 홀수라서 한 번 가져갈 때마다 남은 돌의 홀짝이 바뀌므로, 처음 돌이 짝수 개이면 상근이는 자기 차례마다 짝수 개를 마주하게 된다. 짝수 개가 남은 차례에는 1개나 3개를 가져가도 돌이 남아서 마지막 돌을 가져갈 수 없으니 상...
문제 링크 1. 아이디어 1개 또는 3개씩 돌을 가져가며 마지막 돌을 가져가는 사람이 이기는 돌 게임에서 승자를 구하는 문제다. 1과 3이 모두 홀수라서 한 번 가져갈 때마다 남은 돌의 홀짝이 바뀌므로, 처음 돌이 홀수 개이면 상근이는 매번 짝수 개를 넘기게 되고 창영이는 짝수 개에서 어떻게 가져가도 홀수 개가 남아 0개를 만들 수 없다. 돌...
문제 링크 1. 아이디어 반복문을 활용해서 LoveisKoreaUniversity를 $N$번 출력만 하면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(N)$ $O(1)$ ($N$ = 입력값 n) 3. 코...