전체 글 (164)
다이나믹 프로그래밍 한접시/ [백준] 9084번: 동전 [C#]
2024-05-02 17:33:05

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _9084_boj boj = new _9084_boj();
 
            boj.boj_9084();
 
        }
    }
        internal class _9084_boj
    {
        public void boj_9084()
        {
            int n = int.Parse(Console.ReadLine());
 
            for (int i = 0; i < n; i++)
            {
                int cnt = int.Parse(Console.ReadLine());
                int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int num = int.Parse(Console.ReadLine());
 
                int[] dp = new int[num + 1];
                dp[0] = 1;
                for (int j = 0; j < arr.Length; j++)
                {
                    for (int k = arr[j]; k <= num; k++)
                    {
                        dp[k] += dp[k - arr[j]];
                    }
                    
                }
                Console.WriteLine(dp[num]);
            }
        }
    }
}
    
 cs

한번에 맞아서 오히려 당황했다

 

 

'다이나믹 프로그래밍 한접시' 카테고리의 다른 글

[백준] 2747번: 피보나치 수 [C#]  (0) 2024.05.09
[백준] 15988번: 1, 2, 3 더하기 3 [C#]  (0) 2024.05.03
[백준] 2156번: 포도주 시식 [C#]  (1) 2024.05.01
[백준] 가장 긴 증가하는 부분 수열 4 [C#]  (0) 2024.04.30
[백준] 15486번: 퇴사 2 [C#]  (0) 2024.04.29
다이나믹 프로그래밍 한접시/ [백준] 2156번: 포도주 시식 [C#]
2024-05-01 22:45:12

https://www.acmicpc.net/board/view/139143

이 링크를 타고 들어가면 아주 훌륭한 예제들을 볼 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _2156_boj boj = new _2156_boj();
 
            boj.boj_2156();
 
        }
    }
        internal class _2156_boj
    {
        public void boj_2156()
        {
            int n = int.Parse(Console.ReadLine());
 
            int[] arr = new int[n + 1];
            for (int i =1; i <= n; i++)
            {
                arr[i] = int.Parse(Console.ReadLine());
            }
 
            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = arr[1];
            if (n >= 2)
                dp[2] = arr[1] + arr[2];
 
            for (int i = 3; i <= n; i++)
            {
                dp[i] = Math.Max(Math.Max(arr[i] + dp[i - 2], arr[i] + dp[i - 3] + arr[i - 1]), dp[i - 1]);
 
            }
            Console.WriteLine(dp.Max());
        }
    }
}
 
 cs

 

정말 오랜만에 풀어보는 계단문제였다.

dp[i]의 값을 판별하는 방법 중, dp[i - 1]과도 대소비교를 해줘야 하는 걸 떠올리지 못해서 답을 얻는데 살짝 애를 먹었다.

 

'다이나믹 프로그래밍 한접시' 카테고리의 다른 글

[백준] 15988번: 1, 2, 3 더하기 3 [C#]  (0) 2024.05.03
[백준] 9084번: 동전 [C#]  (0) 2024.05.02
[백준] 가장 긴 증가하는 부분 수열 4 [C#]  (0) 2024.04.30
[백준] 15486번: 퇴사 2 [C#]  (0) 2024.04.29
[백준] 11053번: 가장 긴 증가하는 부분 수열 [C#]  (0) 2024.04.29
다이나믹 프로그래밍 한접시/ [백준] 가장 긴 증가하는 부분 수열 4 [C#]
2024-04-30 23:34:02

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _14002_boj boj = new _14002_boj();
 
            boj.boj_14002();
 
        }
    }
        internal class _14002_boj
    {
        public void boj_14002()
        {
            int n = int.Parse(Console.ReadLine());
 
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
 
            int[] dp = new int[n];
            dp[0] = 1;
 
            for (int i = 1; i < n; i++)
            {
                int max = 0;
                for (int j = i - 1; j >= 0; j--)
                    if (arr[j] < arr[i] && max < dp[j])
                        max = dp[j];
                dp[i] = 1 + max;
            }
            int Max = dp.Max();
            Console.WriteLine(Max);
 
            List<int> arr2 = new List<int>();
 
            for (int i = n - 1; i >= 0; i--)
            {
                if (dp[i] == Max)
                {
                    arr2.Add(arr[i]);
                    Max--;
                }
            }
            arr2.Reverse();
            foreach (var _ in arr2)
                Console.Write(_ + " ");
        }
    }
}
 
 cs

어떻게 하면 부분 수열을 출력할 수 있을지 한참을 고민하다 도저히 좋은 방법이 떠오르지 않아 인터넷에 검색을 해 보왔다.

알고보니 그냥 배열의 밴 마지막 부분부터 다시 훑으며 가장 큰 번호의 원소를 넣고 번호를 1 줄이는 방법을 사용하면 매우 간단하게 답을 얻을 수 있었다....

 

'다이나믹 프로그래밍 한접시' 카테고리의 다른 글

[백준] 9084번: 동전 [C#]  (0) 2024.05.02
[백준] 2156번: 포도주 시식 [C#]  (1) 2024.05.01
[백준] 15486번: 퇴사 2 [C#]  (0) 2024.04.29
[백준] 11053번: 가장 긴 증가하는 부분 수열 [C#]  (0) 2024.04.29
[백준] 11055번: 가장 큰 증가하는 부분 수열 [C#]  (0) 2024.04.29
다이나믹 프로그래밍 한접시/ [백준] 15486번: 퇴사 2 [C#]
2024-04-29 23:18:10

예제가 많아서 좋은 예제 하나만 들고왔습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _15486_boj boj = new _15486_boj();
 
            boj.boj_15486();
 
        }
    }
    internal class _15486_boj
    {
        public void boj_15486()
        {
            int count = int.Parse(Console.ReadLine());
 
            int[] day = new int[count];
            int[] profit = new int[count];
            int[] dp = new int[count + 1];
     
            for (int i = 0; i < count; i++)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                day[i] = input[0];
                profit[i] = input[1];
            }
            for (int i = 0; i < count; i++)
            {
                if (i > 1)
                    dp[i] = Math.Max(dp[i - 1], dp[i]);
                if (i + day[i] <= count)
                    dp[i + day[i]] = Math.Max(dp[i + day[i]], dp[i] + profit[i]);
            }
            Console.WriteLine(dp.Max());
        }
    }
}
 
 cs

 

개념 자체는 몹시 쉽지만 오늘따라 집중이 안되서 푸는데 너무 오래 걸렸다.

 

'다이나믹 프로그래밍 한접시' 카테고리의 다른 글

[백준] 2156번: 포도주 시식 [C#]  (1) 2024.05.01
[백준] 가장 긴 증가하는 부분 수열 4 [C#]  (0) 2024.04.30
[백준] 11053번: 가장 긴 증가하는 부분 수열 [C#]  (0) 2024.04.29
[백준] 11055번: 가장 큰 증가하는 부분 수열 [C#]  (0) 2024.04.29
[백준] 1로 만들기 2 [Python]  (0) 2024.04.29
다이나믹 프로그래밍 한접시/ [백준] 11053번: 가장 긴 증가하는 부분 수열 [C#]
2024-04-29 16:00:05

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _11055_boj boj = new _11055_boj();
 
            boj.boj_11055();
 
        }
    }
        internal class _11055_boj
    {
        public void boj_11055()
        {
            int n = int.Parse(Console.ReadLine());
 
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
 
            int[] dp = new int[n];
            dp[0] = 1;
            
            for (int i = 1; i < n; i++)
            {
                int max = 0;
                for (int j = i - 1; j >= 0; j--)
                    if (arr[j] < arr[i] && max < dp[j])
                        max = dp[j];
                dp[i] = 1 + max;
            }
            Console.WriteLine(dp.Max());
        }
    }
}
 
 cs

 

합을 구하는 문제의 코드에서 조금만 변형을 주면 쉽게 정답을 얻을 수 있다.

'다이나믹 프로그래밍 한접시' 카테고리의 다른 글

[백준] 가장 긴 증가하는 부분 수열 4 [C#]  (0) 2024.04.30
[백준] 15486번: 퇴사 2 [C#]  (0) 2024.04.29
[백준] 11055번: 가장 큰 증가하는 부분 수열 [C#]  (0) 2024.04.29
[백준] 1로 만들기 2 [Python]  (0) 2024.04.29
[백준] 2193번: 이찬수 [C#]  (0) 2024.04.28
다이나믹 프로그래밍 한접시/ [백준] 11055번: 가장 큰 증가하는 부분 수열 [C#]
2024-04-29 15:53:39

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _11055_boj boj = new _11055_boj();
 
            boj.boj_11055();
 
        }
    }
    internal class _11055_boj
    {
        public void boj_11055()
        {
            int n = int.Parse(Console.ReadLine());
 
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
 
            int[] dp = new int[n];
            dp[0] = arr[0];
            
            for (int i = 1; i < n; i++)
            {
                int max = 0;
                for (int j = i - 1; j >= 0; j--)
                    if (arr[j] < arr[i] && max < dp[j])
                        max = dp[j];
                dp[i] = arr[i] + max;
            }
            Console.WriteLine(dp.Max());
        }
    }
}
 
 cs

 

가장 큰 수열의 합을 구하는 것이기 때문에 이전의 값들 중 max의 값을 가져와야 했지만, 그런 과정 없이 가장 가까운 값을 가져와서 합을 해줘서 틀렸었다.

 

 

'다이나믹 프로그래밍 한접시' 카테고리의 다른 글

[백준] 15486번: 퇴사 2 [C#]  (0) 2024.04.29
[백준] 11053번: 가장 긴 증가하는 부분 수열 [C#]  (0) 2024.04.29
[백준] 1로 만들기 2 [Python]  (0) 2024.04.29
[백준] 2193번: 이찬수 [C#]  (0) 2024.04.28
[백준] 11727번: 2*n 타일링 2 [C#]  (0) 2024.04.28
다이나믹 프로그래밍 한접시/ [백준] 1로 만들기 2 [Python]
2024-04-29 14:57:09

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
if __name__ == "__main__":
    num = int(input())
    arr = []
    dp = [0, 0]
 
    for i in range(2, num+1):
        if (i % 6 == 0):
            dp.append(min(dp[int(i / 3)], dp[int(i / 2)]) + 1)
        elif (i % 3 == 0):
            dp.append(min(dp[int(i / 3)], dp[i - 1]) + 1)
        elif (i % 2 == 0):
            dp.append(min(dp[int(i / 2)], dp[i - 1]) + 1)
        else:
            dp.append(dp[i - 1] + 1)
 
    temp = num
    while (temp >= 1):
        if (temp % 6 == 0):
            if (dp[int(temp / 3)] < dp[int(temp / 2)]):
                arr.append(temp)
                temp = int(temp / 3)
            else:
                arr.append(temp)
                temp = int(temp / 2)
        elif (temp % 3 == 0):
            if (dp[int(temp / 3)] < dp[int(temp - 1)]):
                arr.append(temp)
                temp = int(temp / 3)
            else:
                arr.append(temp)
                temp -= 1
        elif (temp % 2 == 0):
            if (dp[int(temp / 2)] < dp[int(temp - 1)]):
                arr.append(temp)
                temp = int(temp / 2)
            else:
                arr.append(temp)
                temp -= 1
        else:
            arr.append(temp)
            temp -= 1
 
    print(dp[num])
    for _ in arr:
        print(_, end=' ')
 cs

 

'다이나믹 프로그래밍 한접시' 카테고리의 다른 글

[백준] 11053번: 가장 긴 증가하는 부분 수열 [C#]  (0) 2024.04.29
[백준] 11055번: 가장 큰 증가하는 부분 수열 [C#]  (0) 2024.04.29
[백준] 2193번: 이찬수 [C#]  (0) 2024.04.28
[백준] 11727번: 2*n 타일링 2 [C#]  (0) 2024.04.28
[백준] 11726번: 2*n 타일링 [C#]  (0) 2024.04.28
다이나믹 프로그래밍 한접시/ [백준] 2193번: 이찬수 [C#]
2024-04-28 23:49:46

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _2193_boj boj = new _2193_boj();
 
            boj.boj_2193();
 
        }
    }
        internal class _2193_boj
    {
        public void boj_2193()
        {
            int n = int.Parse(Console.ReadLine());
 
            long[] dp = new long[n + 1];
            dp[0] = 0;
            dp[1] = 1;
            if (n == 1)
            {
                Console.WriteLine(dp[1]);
                return;
            }
            
            for (int i = 2; i <= n; i++)
            {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            Console.WriteLine(dp[n]);
 
        }
    }
}
 
 cs

 

dp문제 특성 상 값이 매우 빠르게 증가하기 때문에, 올바른 결과를 얻기 위해서는 long 형을 사용해야 한다.

 

'다이나믹 프로그래밍 한접시' 카테고리의 다른 글

[백준] 11055번: 가장 큰 증가하는 부분 수열 [C#]  (0) 2024.04.29
[백준] 1로 만들기 2 [Python]  (0) 2024.04.29
[백준] 11727번: 2*n 타일링 2 [C#]  (0) 2024.04.28
[백준] 11726번: 2*n 타일링 [C#]  (0) 2024.04.28
[백준] 1912번: 연속 합 [C#]  (0) 2024.04.27
다이나믹 프로그래밍 한접시/ [백준] 11727번: 2*n 타일링 2 [C#]
2024-04-28 23:35:15

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _11727_boj boj = new _11727_boj();
 
            boj.boj_11727();
 
        }
    }
    internal class _11727_boj
    {
        public void boj_11727()
        {
            int n = int.Parse(Console.ReadLine());
 
            int[] o_dp = new int[n + 2];
            o_dp[0] = 0;
            o_dp[1] = 1;
            o_dp[2] = 2;
            int[] n_dp = new int[n + 2];
            n_dp[0] = 0;
            n_dp[1] = 0;
            n_dp[2] = 1;
            int[] r_dp = new int[n + 2];
            r_dp[0] = 0;
            r_dp[1] = 1;
            r_dp[2] = 3;
 
            if (n <= 2)
            {
                Console.WriteLine(r_dp[n]);
                return;
            }
 
            for (int i = 3;  i <= n; i++)
            {
                o_dp[i] = (o_dp[i - 1] + o_dp[i - 2]) % 10007;
                n_dp[i] = (r_dp[i - 2] + n_dp[i - 1] + n_dp[i - 2]) % 10007;
                r_dp[i] = (n_dp[i] + o_dp[i]) % 10007;
            }
 
            Console.WriteLine(r_dp[n]);
        }
    }
}
 
 cs

 

저번 문제에서 풀었던 2*1    1*2  타일로만 이루어진 경우의 수를 담은 배열,

2 * 2 타일로도 이루어진 경우의 수를 담는 배열을 만들어서 연산을 해 주었다.

2 * 2 타일을 사용하는 경우는 2*2 타일을 할당 한 후 남은만큼의 공간의 새로운 배열의 값( r_dp[ i - 2 ] )을 넣어주고

2 * 1 타일을 사용하는 경우는 남은 공간의 원래 배열의 값 ( o_dp[ i - 1 ] ) 

1 * 2 타일을 사용하는 경우는 ( o_dp[ i - 2 ] ) 의 값을 사용해서 모두 더했다.

 

 

'다이나믹 프로그래밍 한접시' 카테고리의 다른 글

[백준] 1로 만들기 2 [Python]  (0) 2024.04.29
[백준] 2193번: 이찬수 [C#]  (0) 2024.04.28
[백준] 11726번: 2*n 타일링 [C#]  (0) 2024.04.28
[백준] 1912번: 연속 합 [C#]  (0) 2024.04.27
[백준] 2748번: 피보나치 수 2 [C#]  (0) 2024.04.26
다이나믹 프로그래밍 한접시/ [백준] 11726번: 2*n 타일링 [C#]
2024-04-28 17:32:06

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _11726_boj boj = new _11726_boj();
 
            boj.boj_11726();
 
        }
    }
    internal class _11726_boj
    {
        public void boj_11726()
        {
            int n = int.Parse(Console.ReadLine());
 
            int[] dp = new int[n+1];
            dp[0] = 0;
            dp[1] = 1;
            if (n == 1)
            {
                Console.WriteLine(dp[n]);
                return;
            }
            dp[2] = 2;
 
            if (n <= 2)
            {
                Console.WriteLine(dp[n]);
                return;
            }
 
            for (int i = 3; i <= n; i++)
            {
                dp[i] = (dp[i - 1] + dp[i - 2]) % 10007 ;
            }
            Console.WriteLine(dp[n]);
        }
    }
}
 
 cs

 

3*n타일 문제를 풀던 생각에 사로잡혀 어떠한 규칙성을 찾아보려고 애를 써보았지만, 결국 전단계 + 전전단계 였다는 것을 알게되고 좌절한 나.

 

'다이나믹 프로그래밍 한접시' 카테고리의 다른 글

[백준] 2193번: 이찬수 [C#]  (0) 2024.04.28
[백준] 11727번: 2*n 타일링 2 [C#]  (0) 2024.04.28
[백준] 1912번: 연속 합 [C#]  (0) 2024.04.27
[백준] 2748번: 피보나치 수 2 [C#]  (0) 2024.04.26
[백준] 1932번: 정수 삼각형 [C#]  (1) 2024.04.25

티스토리툴바