1514. Path with Maximum Probability
간선에 확률이 있는 그래프가 주어진다. 시작점에서 끝점으로 갈 때 확률의 최대를 구하는 문제. 그냥 다익스트라를 돌려주면 된다. 일반 다익스트라가 합이 최소가 되게 한다면 여기서는 곱이 최대가 되게 뽑아주면 된다.
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
304 303 592. Fraction Addition and Subtraction
분수들의 식이 주어질 때 계산하는 문제 스트링 파싱 후 계산하면 된다. 초등학교 때 배운 분수의 덧셈 그대로 구현하면 되는데 분모는 최소공배수로 맞추고 분자끼리 더한 후 최대공약수로 분자와 분모를 각각 나눠주면 된다. 정규표현식으로 파싱이 깔끔하게 되는거 같은데 난 무식하게... 하나씩 파싱했다 ㅋㅋ
302 476. Number Complement
수가 주어질 때 complement를 구하는 문제. 1이 0이 되고 0이 1이 되려면?? XOR를 쓰면 된다. 자릿수를 올라가면서 1과 XOR를 하면 1은 0이 되고 0은 1이 된다.
301 664. Strange Printer
한 문자를 죽 이어 붙이거나 특정 범위의 문자열을 교체하는 2가지 연산을 할 때 최소한의 연산으로 문자열을 만드는 횟수를 찾는 문제. 약간 분할 정복, 완전탐색 느낌이 나는데 쉽지 않다. 일단 양옆이 같은 문자인 경우 중간을 바꿔치기 했다고 생각할 수 있다. 그 외의 경우는 이어 붙여야 한다. 따라서 문제를 나눠볼 수 있는데 맨 앞과 같은 문자가 중간에 나…
300 1140. Stone Game II
돌들이 있고 Alice와 Bob이 차례로 돌을 가져갈 때 최대가 되게 가져가는 점수를 구하는 문제. 1 - 2*M개의 돌을 가져갈 수 있다. 이런 게임류 문제가 익숙하지 않으면 꽤 어렵다. 이렇게 두면 좀 보일까 싶은데 쉽지 않다. 여기서 Alice와 Bob의 관계를 생각해봐야 하는데 Alice는 Bob이 최소로 가져가게 골라야 한다. 그럼 Alice가 가…
299 650. 2 Keys Keyboard
복사, 붙여넣기만 가능한 키보드에서 특정 길이를 만드는 최소 횟수를 구하는 문제 일단 간단히 DP로 풀리긴 한다. dp[i][j] = i길이를 j만큼 붙여넣어 만들때 최소 횟수. O(n^2) 그런데 여기서 수학적으로 접근하면 O(n)으로 가능하다. 자세한건 에디토리얼 참고.
298 264. Ugly Number II
소인수가 2, 3, 5로만 이루어진 수를 ugly number라 할 때 n번째 ugly number를 구하는 문제 n범위가 작아서 무식하게 구해도 통과는 된다. 좀 더 O(n)으로 잘 구해볼 수 있을까.. 약간의 dp를 쓸 수 있다. 일단 다음 수는 이전의 ugly number들 뒤에 2, 3, 5를 곱한 수가 된다. 그 중 제일 작은 수가 다음 수가 된다…
297 1937. Maximum Number of Points with Cost
2차원에서 점수를 먹는 문제. 먹을 때 이전에 먹은 열과 비교해서 그 차이만큼은 빼야 한다. 3차원 dp는 쉽다. 다만 시간 초과. 2차원으로 어떻게 하면 줄일 수 있을까? 왼쪽에서 왔을 때의 최대와 오른쪽에서 왔을 때의 최대를 같이 구해서 그 중 최대값으로 업데이트하면 된다. 에디토리얼 참고. 간단하게 설명하면 left_max[i]는 i보다 왼쪽의 점수 …
296 624. Maximum Distance in Arrays
배열이 여러개 주어질 때 서로 다른 배열끼리 가장 큰 원소의 차이를 출력하는 문제. 그리디? 라고도 볼 수 있다. 일단 차가 가장 크려면 각각 다른 배열의 최대와 최소를 빼줘야 한다. 중간에 있는 원소는 필요 없다. 간단하고 직관적으로 짜려면 모든 배열의 최대와 최소를 구한 뒤 같은 배열이라면 두번째 최대 혹은 두번째 최소로 답을 구할 수 있긴 하다. 힙으…
295 860. Lemonade Change
5달러로 레모네이드를 팔 때 거스름돈을 줄 수 있는지 판단하는 문제. 손님은 5, 10, 20 달러 지폐만 사용한다. 그냥 단순 시뮬레이션. 약간의 그리디도 들어가는데 20달러를 냈을 때 10달러가 있다면 10달러 포함해서 거슬러 주는게 무조건 이득이다. 나머지는 5달러로 거슬러 주고 5달러 지폐가 음수가 되면 False를 리턴하면 된다.