DP
-
[Algo Rhythm🕺💃] BOJ 2225 - 합분해Algo Rhythm🕺💃/BOJ 2021. 7. 22. 22:15
💫문제 분석 입력으로 주어지는 두 정수를 각각 N,K (1≤N,K≤200)라고 하자. 그리고 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 f(N,K)라고 하자. 마지막으로 N을 만들기 위해 더해지는 K개의 정수들을 순서대로 I1,I2,...,IK라고 하자. f(N,K)의 규칙을 파악하기 위해 f(2,3)를 구하는 과정을 분석해보자. f(2,3)은 아래와 같이 6이다. 이때 I1과 나머지 I2,I3의 관계를 파악해보자. I1=0 일때 I2,I3를 구하는 것은 f(2,2)을 구하는 것과 같다. (1이 적힌 파란 원으로 표시함) I1=1 일때 I2,I3를 구하는 것은 f(1,2)..
-
[Algo Rhythm🕺💃] BOJ 9095 - 1, 2, 3 더하기Algo Rhythm🕺💃/BOJ 2021. 6. 29. 00:06
💫문제 분석 테스트 케이스의 개수를 t, 각 테스트 케이스마다 주어지는 정수를 n(1≤n<11)이라고 하자. 그리고 n을 1, 2, 3의 합으로 나타내는 방법의 수를 f(n)이라고 하자. 각 테스트케이스마다 f(n)을 출력해야 하며, 합을 나타낼 때는 수를 1개 이상 사용해야 한다. f(n)은 1부터 차례대로 아래와 같다. 이때 파란색 동그라미로 표시된 수들을 관찰하면 분명히 연쇄적인 관계가 있다는 것을 알 수 있다. 따라서 이 문제는 그 '연쇄적인 관계'를 이용하여 해결할 수 있다. 🔥문제 풀이 앞서 언급한 연쇄적인 관계는 다음과 같다. $\begin{matrix} f(i) &=& \sum_{j = 1}^3 g(i, j) & (1\le i\lt 11, i ..
-
[Algo Rhythm🕺💃]BOJ 1620 - 정상 회담2Algo Rhythm🕺💃/BOJ 2021. 3. 12. 15:05
문제 분석 문제를 분석하는 효과적인 방법들 중 하나는 그림으로 표현해보는 것이다. 이 문제에서 N = 0, 2, 4, 6 일때 완벽하게 악수하는 경우들과 그 수를 그림으로 표현하면 아래와 같다. (이때 각 국가의 대표는 노드로 표현했다.) 그림에서 검은색 노드와 흰색 노드가 연결된 선분을 기준으로 왼쪽 영역을 l, 오른쪽 영역을 r라고 하자. 그리고 a개의 노드들이 완벽하게 악수할 수 있는 경우의 수를 f(a)라고 하자. 그렇다면 N =0, 2, 4, 6일때 완벽하게 악수할 수 있는 경우의 수는 아래와 같은 규칙이 있음을 알 수 있다. 이 규칙을 점화식으로 표현하면 다음과 같다. $f(N)= \begin{cases} 1, & if\ n = 0\\ \sum_{i=0}^{N-2} f(i) \t..
-
[Algo Rhythm🕺💃]BOJ 14501 - 퇴사Algo Rhythm🕺💃/BOJ 2021. 3. 11. 00:41
문제분석 백준이는 i(1≤i≤N)번째 날의 일을 하느냐 마느냐에 따라 얻을 수 있는 이익이 다르다. 단순히 생각하면 i번째 날의 일을 하는 경우와 안 하는 경우로 나눠서 모든 경우를 살핀 뒤 그 중 최대의 이익을 구하면 될 것 같다. 사실 그래도 된다. 하지만 조금 더 생각해보면 보다 더 효율적인 방법이 있다는 것을 알 수 있다. 앞서 말했듯이 백준이는 i번째 날의 일을 하느냐 마느냐에 따라 얻을 수 있는 이익이 다르다. 자세히 말하면 만약 i번째 날의 일을 한다면 i+T[i]번째 날의 일부터 하느냐 마느냐를 선택할 수 있고 만약 i번째 날의 일을 하지 않는다면 i+1번째 날의 일부터 하느냐 마느냐를 선택할 수 있다. 즉, 백준이가 i번째 날의 일을 하느냐 마느냐를 결정..
-
[Algo Rhythm🕺💃] BOJ 17528. Two MachinesAlgo Rhythm🕺💃/BOJ 2020. 8. 26. 21:06
📚 문제 설명 스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 ti를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나를 선택할 수 있다. 작업 ti를 완료하기 위해 머신 A를 선택하면 ai시간이 걸리고 머신 B를 선택하면 bi 시간이 걸린다. 각 머신은 어느 순간에 최대 하나의 작업만 수행할 수 있으며, 한 작업이 시작되면 그 작업을 완료하기 전까지 다른 작업을 그 머신에서 수행할 수 없다. SOPT 는 모든 작업을 완료하기 위한 최소의 완료 시간을 구하고자 한다. 예를 들어, 세 개의 작업이 t1, t2, t3가 주어져 있고 a1 = 2, b1 = 3, a2 = 5, ..
-
[Algo Rhythm🕺💃] BOJ 17626. Four SquaresAlgo Rhythm🕺💃/BOJ 2020. 8. 24. 15:06
📚 문제 설명 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125^2 + 6^2 + 1^2 + 1^2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105^2 + 15^2 + 8^2 + 5^2. 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램..
-
[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 도둑질Algo Rhythm🕺💃/Programmers 2020. 8. 8. 22:49
📚 문제 설명 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. 🎯 어떻게 풀었나 Backtracking을 이용한 첫번째 시도 (0/ 100) => 정확성은 모두 시간 초과, 효율성은 모두 통과 🙅♂️🙅♀️🙅 class Solution { private..
-
[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 등굣길Algo Rhythm🕺💃/Programmers 2020. 8. 6. 15:21
📚 문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. 제한사항 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다. m과..