"꾸준하고 완벽한 한 걸음"

PS/Baekjoon Online Judge 665

[백준 17554] City of Lights [Java]

문제https://www.acmicpc.net/problem/17554 풀이처음에는 켜져있는 N개의 전구에 대해 K번 동안 N이하의 i배수 번째의 전구들을 토글할 때 최대한 많이 꺼진 전구의 수를 구하는 문제다.처음에는 전구를 전부 켜주고, boolean[] light = new boolean[N]; Arrays.fill(light, true);K개의 i를 입력 받아, i의 배수들을 전부 토글하면 된다. int res = 0; while (K-- > 0) { final int i = Integer.parseInt(br.readLine()); // Solve int cur = -1; ..

[백준 10657] Cow Jog [Java]

문제https://www.acmicpc.net/problem/10657 풀이소의 위치가 증가하는 순서대로 소의 위치와 속도가 주어진다.소의 속도가 빠르다면 결국 자신보다 앞에 있는 소를 추월하게 되는데 이 때 같은 그룹이 된다.같은 그룹이 되면, 가장 느린 소의 속도에 맞춰 이동한다.따라서 가장 뒤에 있는 소를 기준으로 속도가 같거나 작다면, 새로운 그룹이 될 수 있다. int cnt = 1, curSpeed = speeds[N - 1]; for (int i = N - 2; i >= 0; --i) { if (speeds[i] 소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-j..

[백준 01935] 후위 표기식2 [Python]

문제https://www.acmicpc.net/problem/1935 풀이스택을 사용해 후위표현식을 구현하면 된다.우선, 수식의 문자에 대응하는 숫자를 매핑해주자. num = {} for i in range(N): num[chr(ord("A") + i)] = int(input())연산 기호를 입력 받기 전 까지 모든 숫자를 스택에 저장해주고,연산 기호를 입력받으면 스택에 저장해둔 두 수를 꺼내 계산을 한 뒤 다시 스택에 저장하면 된다.이 과정을 반복하면 스택에는 후위 표현식에 대한 계산 결과가 남는다. # Solve stack = [] for f in F: if f.isalpha(): stack.append(num[f]) ..

[백준 22943] 수 [Java]

문제https://www.acmicpc.net/problem/22943 풀이0 ~ 9 중에서 서로 다른 K개를 골라 만들 수 있는 수 중 다음을 만족하는 수를 구해야 한다.서로 다른 두 개의 소수의 합으로 나타낼 수 있어야 하고,M으로 나누어 떨어지지 않을 때 까지 나눈 수가 두 개의 소수의 곱인 경우이어야 한다.구현할 부분이 많지만, 하나씩 해결해보자.0 ~ 9로 K자리 수 만들기우선 0 ~ 9 중 K개를 골라 수를 만들어야 한다.숫자를 한 번씩 만 사용해야 하고, 첫 번째는 0이 올 수 없다. private static void solve(int digit, int num) { if (digit == 0) { // base case } fo..

[백준 02436] 공약수 [Python]

문제https://www.acmicpc.net/problem/2436 풀이두 수 A, B의 GCD, LCM이 주어질 때, 두 수의 합이 최소가 되는 수를 구하는 문제다.이때 두 수의 범위 2 ~ 1억에 대해 GCD, LCM을 전부 구해 비교하는 방법은 시간 초과가 발생한다.탐색 범위를 좁혀보자.$G = GCD(A, B), L = LCM(A, B)$일 때, $AB = GL$, $A = Gx$, $B = Gy$이므로 $AB = G^2xy = GL, xy = \frac{L}{G} = K$가 성립한다.K의 모든 약수 쌍 중 $GCD(A, B) = G*GCD(x, y)$를 만족해야 하므로, $GCD(x, y) = 1$인 약수만 해당된다. K = LCM // GCD x, y = 0, 0 for d ..