코기장 by 코기장

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

import java.util.Scanner;
 
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        sc.nextLine();
        
        String arr1;
        String arr2;
        
        
        
        for (int i =0; i < N; i++)
        {
            boolean res = true;
            int[] alphabet = new int[26];
            String[] input = sc.nextLine().split(" ");
            arr1 = input[0];
            arr2 = input[1];
            
            for (int j = 0; j < arr1.length(); j++)
                alphabet[arr1.charAt(j) - 'a']++;
            
            for (int k = 0; k < arr2.length(); k++)
                alphabet[arr2.charAt(k) - 'a']--;
            
            for (int l = 0; l < 26; l++)
                if (alphabet[l] != 0)
                    res = false;
                
            System.out.println(res ? "Possible" : "Impossible");
        }
    }
}
 
Colored by Color Scripter

cs

매 루프 반복 후 boolean 변수 res를 다시 true로 초기화 해줘야 하는데 그거를 깜빡해서 오류가 났었다.

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

[백준] 1919번 애너그램 만들기 [Java] (1)	2024.04.19
[백준] 13300번: 방 배정 [Java] (0)	2024.04.19
[백준] 두 수의 합 [C#] (1)	2024.04.19
[백준] 1475번: 방 번호 [Java] (0)	2024.04.18
[백준] 10808번: 알파벳 개수 [Java] (0)	2024.04.18

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

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String[] input = sc.nextLine().split(" ");
        int count = Integer.parseInt(input[0]);
        int max = Integer.parseInt(input[1]);
        
        
        int[][] arr = new int[2][6];
        
        for (int i =0; i < count; i++ )
        {
            String[] student = sc.nextLine().split(" ");
            int gender = Integer.parseInt(student[0]);
            int grade = Integer.parseInt(student[1]);
            arr[gender][grade-1]++;
        }
        int cnt = 0;
        
        for (int i =0; i < 2; i++)
        {
            for (int j = 0; j < 6; j++)
            {
                cnt+= (arr[i][j] + (max - 1)) / max;
            }
        }
        
        System.out.println(cnt);
    }
}
 
Colored by Color Scripter

cs

필요한 방의 개수를 셀 때, 배열의 현재값에 더하는 값을 예제에 맞춰 2로 하드코딩해뒀었는데, 그거때문에 틀렸었다.

2를 max - 1로 바꾼 이후에는 정답을 받았다.

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

[백준] 1919번 애너그램 만들기 [Java] (1)	2024.04.19
[백준] 11328번: StrFry [Java] (0)	2024.04.19
[백준] 두 수의 합 [C#] (1)	2024.04.19
[백준] 1475번: 방 번호 [Java] (0)	2024.04.18
[백준] 10808번: 알파벳 개수 [Java] (0)	2024.04.18

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 _3273_boj
    {
        public void boj_3273()
        {
            int n = int.Parse(Console.ReadLine());
 
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
 
            List<int> arr = new List<int>();
 
            for (int i = 0; i < n; i++)
                arr.Add(input[i]);
 
            int x = int.Parse(Console.ReadLine());
 
            int res = 0;
            for (int i = 0; i < n; i++)
            {
                if (arr[i] == x - arr[i])
                    continue;
                if (arr.Contains(x - arr[i]))
                    res++;
            }
 
            Console.WriteLine(res / 2);
        }
 
    }
}
 
Colored by Color Scripter

cs

최대한 배열로 풀어보려고 했는데, 못해먹겠어서 리스트를 이용해서 해결했다.

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

[백준] 1919번 애너그램 만들기 [Java] (1)	2024.04.19
[백준] 11328번: StrFry [Java] (0)	2024.04.19
[백준] 13300번: 방 배정 [Java] (0)	2024.04.19
[백준] 1475번: 방 번호 [Java] (0)	2024.04.18
[백준] 10808번: 알파벳 개수 [Java] (0)	2024.04.18

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);
    }
 
}
 
Colored by Color Scripter

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

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 + " ");
    }
}
 
Colored by Color Scripter

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

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);
        }
    }
}
 
Colored by Color Scripter

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

예전에 풀었던 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]);
 
 
            }
        }
    }
}
 
Colored by Color Scripter

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

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]);
        }
    }
}
 
Colored by Color Scripter

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

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

단순히 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());
        }
    }
}
 
Colored by Color Scripter

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

점화식: 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]);
        }
    }
}
 
Colored by Color Scripter

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

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

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

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

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

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

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

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

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

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

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

티스토리툴바