전체 글 (162)
배열 한접시/ [백준] 1475번: 방 번호 [Java]
2024-04-18 22:18:41

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
import java.util.Scanner;
 
public class Main{
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int input = sc.nextInt();
        
        int[] arr = new int[10];
        
 
        while (input != 0)
        {
            int num = input % 10;
            
            if (num == 9 && arr[num] > arr[6])
                arr[6]++;
            else if(num == 6 && arr[num] > arr[9])
                arr[9]++;
            else
                arr[num]++;
            
            input /= 10;
        }
        
        int max = 0;
        for (int i : arr)
            max = Math.max(max,  i);
        
        System.out.println(max);
    }
 
}
 
 cs

 

9와 6을 돌려쓸 수 있는 조건이 달려있는 문제다.

어떻게 하면 효율적으로 풀 수 있을지 고민하다 그냥 9번방(혹은 6번방)의 값이 반대쪽 방의 값보다 크다면 반대쪽 방의 값을 증가시키고, 아니면 자신의 방의 크기를 증가시키는 방법을 사용했다.

 

 

'배열 한접시' 카테고리의 다른 글

[백준] 1919번 애너그램 만들기 [Java]  (1) 2024.04.19
[백준] 11328번: StrFry [Java]  (0) 2024.04.19
[백준] 13300번: 방 배정 [Java]  (0) 2024.04.19
[백준] 두 수의 합 [C#]  (1) 2024.04.19
[백준] 10808번: 알파벳 개수 [Java]  (0) 2024.04.18
배열 한접시/ [백준] 10808번: 알파벳 개수 [Java]
2024-04-18 21:31:37

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Scanner;
 
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int[] arr = new int[26];
        
        String input = sc.nextLine();
        
        for (int i =0; i < input.length(); i++)
            arr[input.charAt(i) - 'a']++;
        System.out.println(123);
        
        for (int s : arr)
            System.out.print(s + " ");
    }
}
 
 cs

 

문자열 변수를 배열처럼 바로 인덱싱할 수 있었던 C#에 비해 java는 charAt() 메서드를 사용해야 한다는걸 알게 되었다.

 

'배열 한접시' 카테고리의 다른 글

[백준] 1919번 애너그램 만들기 [Java]  (1) 2024.04.19
[백준] 11328번: StrFry [Java]  (0) 2024.04.19
[백준] 13300번: 방 배정 [Java]  (0) 2024.04.19
[백준] 두 수의 합 [C#]  (1) 2024.04.19
[백준] 1475번: 방 번호 [Java]  (0) 2024.04.18
다이나믹 프로그래밍 한접시/ [백준] 1149번: RGB거리 [C#]
2024-04-17 15:12:24

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace 연습장
{
    internal class _1149_boj
    {
        public void boj_1149()
        {
            int N = int.Parse(Console.ReadLine());
 
            int[,] dp = new int[N + 1, 3];
            dp[0, 0] = 0;
            dp[0, 1] = 0;
            dp[0, 2] = 0;
 
            for (int i = 1; i <= N; i++)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                dp[i, 0] = input[0] + Math.Min(dp[i - 1, 1], dp[i - 1, 2]);
                dp[i, 1] = input[1] + Math.Min(dp[i - 1, 0], dp[i - 1, 2]);
                dp[i, 2] = input[2] + Math.Min(dp[i - 1, 0], dp[i - 1, 1]);
 
            }
 
            int res = int.MaxValue;
            for (int i = 0; i < dp.GetLength(1); i++)
            {
                res = Math.Min(dp[N, i], res);
            }
            Console.WriteLine(res);
        }
    }
}
 
 cs

 

i번째 집의 색은 i - 1번째, i + 1번째 집의 색과 다르기만 하면 색을 어떻게 사용하던지 상관이 없다.

이걸 이용해서 코드를 짜주었다.

 

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

[백준] 1932번: 정수 삼각형 [C#]  (1) 2024.04.25
[백준] 11659번: 구간 합 구하기 4 [Java]  (0) 2024.04.24
[백준] 9095번: 1, 2, 3 더하기 [C#]  (0) 2024.04.16
[백준] 1463번: 1로 만들기 [C#]  (0) 2024.04.15
[백준] 14501번: 퇴사 [C#]  (0) 2024.04.14
다이나믹 프로그래밍 한접시/ [백준] 9095번: 1, 2, 3 더하기 [C#]
2024-04-16 16:11:11

 

예전에 풀었던 1, 2, 5로 숫자 만들기 문제와 비슷하지만, 이번에는 숫자의 조합을 다르게 하면 다른 경우의 수로 인정을 해주는 문제이다.

이전에는 dp[i] += dp[i - n] ( i = dp의 현재 인덱스, n은 1, 2, 5 중 하나) 로 풀었지만, 이번에는 다른 접근이 필요할 것 같다.

 

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace 연습장
{
    internal class _9095_boj
    {
        public void boj_9095()
        {
            int N = int.Parse(Console.ReadLine());
 
            List<int> dp = new List<int>();
            dp.Add(0);
            dp.Add(1);
            dp.Add(2);
            dp.Add(4);
 
            for (int i = 0; i < N; i++)
            {
                int input = int.Parse(Console.ReadLine());
 
                if (input <= 3)
                {
                    Console.WriteLine(dp[input]);
                    continue;
                }
 
                for (int j = dp.Count; j <= input; j++)
                {
                    dp.Add(dp[j - 3] + dp[j - 2] + dp[j - 1]);
                }
 
                Console.WriteLine(dp[input]);
 
 
            }
        }
    }
}
 
 cs

 

열심히 규칙을 찾아보려고 그림을 그려 보던 중 3, 2, 1 칸 전의 값들의 합이 이번 칸의 값이라는걸 알아냈다.

이후 코드로 구현했더니 정답이었다.

 

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

[백준] 11659번: 구간 합 구하기 4 [Java]  (0) 2024.04.24
[백준] 1149번: RGB거리 [C#]  (0) 2024.04.17
[백준] 1463번: 1로 만들기 [C#]  (0) 2024.04.15
[백준] 14501번: 퇴사 [C#]  (0) 2024.04.14
[백준] 2133번: 타일 채우기 [C#]  (0) 2024.04.13
다이나믹 프로그래밍 한접시/ [백준] 1463번: 1로 만들기 [C#]
2024-04-15 00:33:32

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace 연습장
{
    internal class _1463_boj
    {
        public void boj_1463()
        {
            int X = int.Parse(Console.ReadLine());
 
            int[] dp = new int[X + 1];
 
            dp[1] = 0;
 
            for (int i = 2; i < dp.Length; i++)
            {
                if (i % 6 == 0)
                    dp[i] = Math.Min(1 + dp[i / 3], 1 + dp[i / 2]);
                else if (i % 3 == 0)
                    dp[i] = Math.Min(1 + dp[i / 3], 1 + dp[i - 1]);
                else if (i % 2 == 0)
                    dp[i] = Math.Min(1 + dp[i / 2], 1 + dp[i - 1]);
                else
                    dp[i] = 1 + dp[i - 1];
 
            }
 
            Console.WriteLine(dp[X]);
        }
    }
}
 
 cs

 

6의 배수에 대한 처리를 하지 않으면 문제가 생기므로 6의 배수일 경우 2로 나눈 경우와 3으로 나눈 경우를 비교해서 더 작은 것을 넣어줘야 한다.

 

 

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

[백준] 1149번: RGB거리 [C#]  (0) 2024.04.17
[백준] 9095번: 1, 2, 3 더하기 [C#]  (0) 2024.04.16
[백준] 14501번: 퇴사 [C#]  (0) 2024.04.14
[백준] 2133번: 타일 채우기 [C#]  (0) 2024.04.13
[백준] 1965번: 상자 넣기 [C#]  (0) 2024.04.11
다이나믹 프로그래밍 한접시/ [백준] 14501번: 퇴사 [C#]
2024-04-14 15:17:28

예제가 많아서 주요한 예제 하나만 들고왔습니다

단순한 다이나믹 프로그래밍 처럼 보이지만, 브루트포스의 성질도 띄고있는 문제입니다.

단순히 n일 후의 이익만 계산하면 안되고,  n + a의 이익도 계산해서 최대의 값을 구해야 하는 문제입니다.

 

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace 연습장
{
    internal class _14501_boj
    {
        public void boj_14501()
        {
            int N = int.Parse(Console.ReadLine());
 
            int[] dp = new int[N + 1];
            int[] time = new int[N + 1];
            int[] value = new int[N + 1];
 
            for (int i  = 1; i < dp.Length; i++)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                time[i] = input[0];
                if (i + time[i] <= dp.Length)
                    value[i] = input[1];
                else
                    value[i] = 0;
            }
 
            for (int i = 1; i < dp.Length; i++)
            {
                dp[i] = Math.Max(dp[i], value[i]);
                for (int j = i + time[i]; j < dp.Length; j++)
                { 
                    if (j < dp.Length)
                    {
                        dp[j] = Math.Max(dp[j], dp[i] + value[j]);
                    }
                }
            }
            
            Console.WriteLine(dp.Max());
        }
    }
}
 
 cs

 

for문을 한번만(i for문) 돌렸을 때는, 위의 예제에서 출력이 80이 나왔다.

6일차까지 상담을 들어 60의 이익을 얻고, 바로 2일치 상담을 들어 80이 최고 이익이라는 결과가 나왔기 때문이다.

하지만 문제의 정답은 90이다. 즉, 7일차의 20짜리 상담을 포기하고, 8일차의 30짜리 상담을 들어야지 올바른 값을 얻을 수 있다는 것이다.

이것을 구현하기 위해서 for문을 한개 더 만들어 j일(여기서는 6일)부터 퇴사일까지 모든 상담의 이익을 비교해서 가장 큰 이익을 얻어주었다.

 

 

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

[백준] 9095번: 1, 2, 3 더하기 [C#]  (0) 2024.04.16
[백준] 1463번: 1로 만들기 [C#]  (0) 2024.04.15
[백준] 2133번: 타일 채우기 [C#]  (0) 2024.04.13
[백준] 1965번: 상자 넣기 [C#]  (0) 2024.04.11
[백준] 1890번: 점프 [C#]  (0) 2024.04.10
다이나믹 프로그래밍 한접시/ [백준] 2133번: 타일 채우기 [C#]
2024-04-13 22:19:17

 

점화식: dp[N] = dp[N-2] * 3 + ∑(dp[i] * 2) (i 는 0이 될때까지 2씩 감소)

 

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace 연습장
{
    internal class _2133_boj
    {
        public void boj_2133()
        {
            int N = int.Parse(Console.ReadLine());
 
            int[] dp = Enumerable.Repeat(0, 31).ToArray();
            dp[0] = 1;
            dp[2] = 3;
 
            for (int a = 4; a <= N; a += 2)
            {
                dp[a] = dp[a - 2] * 3;
                for (int i = a - 2; i >= 2; i -= 2)
                {
                    dp[a] += dp[i - 2] * 2;
                }
            }
 
            Console.WriteLine(dp[N]);
        }
    }
}
 
 cs

 

나는 이에 대한 실로 놀라운 증명법을 발견했다. (하지만) 시간이 부족하여 이를 적지 않겠다.

 

 

 

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

[백준] 1463번: 1로 만들기 [C#]  (0) 2024.04.15
[백준] 14501번: 퇴사 [C#]  (0) 2024.04.14
[백준] 1965번: 상자 넣기 [C#]  (0) 2024.04.11
[백준] 1890번: 점프 [C#]  (0) 2024.04.10
[백준] 2294번: 동전 2 [C#]  (0) 2024.04.09
하루 한 접시/ [백준] 10872번: 팩토리얼 [Python]
2024-04-12 23:57:11

복습하면서 그냥 풀어봤다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def factorial(number):
    if (number == 0):
        return 1
    if (number == 1):
        return 1
    res = 1
    for i in range(2, number+1):
        res *= i
    return res
 
number = int(input())
 
res = factorial(number)
 
print(res)
 cs

'하루 한 접시' 카테고리의 다른 글

[백준] 1100번: 하얀 칸 [Python]  (0) 2024.04.22
[백준] 1158번: 요세푸스 문제 [C#]  (0) 2024.04.20
[백준] 1092번: 배 [C#]  (0) 2024.04.05
[백준] 18258번: 큐 2 [C#]  (0) 2024.04.03
[백준] 12789번: 도키도키 간식드리미 [C#]  (0) 2024.04.03
다이나믹 프로그래밍 한접시/ [백준] 1965번: 상자 넣기 [C#]
2024-04-11 23:50:26

 

말이 참 복잡하지만, 결국 한 상자에 들어갈 수 있는 가장 많은 상자의 수를 구하는 문제이다.

상자는 자신보다 번호가 큰 상자 어디든 들어갈 수 있기 때문에, 주의해야한다.

 

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace 연습장
{
    internal class _1965_boj
    {
        public void boj_1965()
        {
            int N = int.Parse(Console.ReadLine());
 
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
 
            int[] dp = new int[N];
            for (int i = 0; i < N; i++)
            {
                dp[i] = 1;
            }
// int[] dp = Enumerable.Repeat(1, N).ToArray();
 
 
            for (int i =1; i < N; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (arr[j] < arr[i])
                        dp[i] = Math.Max(1 + dp[j], dp[i]);
                }
            }
 
            Console.WriteLine(dp.Max());
        }
    }
}
 
 cs
 
 
  

 

문제를 보고 이해가 너무 안가서 코파일럿의 도움을 받아 간신히 이해를 했다.

코드 자체는 막힘없이 쉽게 써졌고, 예제는 전무 맞았으나 체점에는 틀렸습니다가 계속 나왔다.

알고보니 처음에 나는 dp의 0번지에만 1을 넣었는데, 이것은 0번 박스가 반드시 포함이 된다는 가정하에 작성되는 코드였다.

박스가 몇번지에 있든 가장 중첩이 많이된 박스의 중첩 수를 출력하는 것이므로 모든 배열의 원소를 1로 초기화하고 진행했더니 정답이었다.

 

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

[백준] 14501번: 퇴사 [C#]  (0) 2024.04.14
[백준] 2133번: 타일 채우기 [C#]  (0) 2024.04.13
[백준] 1890번: 점프 [C#]  (0) 2024.04.10
[백준] 2294번: 동전 2 [C#]  (0) 2024.04.09
[백준] 9461번: 파도반 수열 [C#]  (0) 2024.04.09
다이나믹 프로그래밍 한접시/ [백준] 1890번: 점프 [C#]
2024-04-10 23:21:08

 

게임 판에서 해당 칸의 숫자만큼 점프를 뛰어서 맨 마지막 자리에 도달할 경우의 수를 출력하는 문제이다.

경로의 개수는 2의 63제곱 -1 만큼 주어지는 것을 유의해야 한다. 

 

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace 연습장
{
    internal class _1890_boj
    {
        public void boj_1890()
        {
            int N = int.Parse(Console.ReadLine());
 
            int[,] dp = new int[N, N];
            dp[0, 0] = 1;
 
            int[,] arr = new int[N, N];
 
            for (int i = 0; i < N; i++)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                for (int j = 0; j < N; j++)
                    arr[i, j] = input[j];
            }
 
            for (int a = 0; a < N; a++)
            {
                for (int b = 0; b < N; b++)
                {
                    if (a == 3 && b == 3)
                        break;
                    if (dp[a, b] == 0)
                        continue;
                    if (a + arr[a, b] <= N - 1)
                        dp[a + arr[a, b], b] += dp[a, b];
                    if (b + arr[a, b] <= N - 1)
                        dp[a, b + arr[a, b]] += dp[a, b];
                }
            }
 
            Console.WriteLine(dp[N - 1, N - 1]);
 
        }
 
    }
}
 
 cs

 

지금까지 풀어왔던 dp문제들은 뒤의 칸이 전의 칸의 값을 참조해와서 증/감산이 이루어졌다.

하지만 이번 문제는 전의 칸이 뒤의 칸에 직접 영향을 주는(직접 가/감을 하는) 문제였던 거 같다.

 

마지막 칸에 도달하면 루프에서 벗어나야 하는데, 벗어나는 코드를 만들지 않아서 값이 이상하게 나왔었다. 

예제로 보면 계산을 잘 해서 마지막 칸에 3이 들어갔었지만, 마지막 칸이 자기 자신의 값으로 2번 더해서 12라는 이상한 값이 나왔던 것이었다.

 

또한, long형으로 주어지는 입력을 모르고 int형으로 받아와서 오류가 났었다.

문제를 더욱 꼼꼼히 읽어보는 습관을 길러야겠다.

 

 

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

[백준] 2133번: 타일 채우기 [C#]  (0) 2024.04.13
[백준] 1965번: 상자 넣기 [C#]  (0) 2024.04.11
[백준] 2294번: 동전 2 [C#]  (0) 2024.04.09
[백준] 9461번: 파도반 수열 [C#]  (0) 2024.04.09
[백준] 9465번: 스티커 [C#]  (0) 2024.04.09

티스토리툴바