전체 글 (162)
다이나믹 프로그래밍 한접시/ [백준] 1932번: 정수 삼각형 [C#]
2024-04-25 23:30:52

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

 

처음에는 j번째 행이 이후 행의 값들을 모두 순회하며 연산을 진행하는걸로 구현했었다.

결과가 이상하게나오는걸 보고 문제를 다시 읽어본다음, j번째 행이 다음 행의 같은 열, 1칸 뒤의 열만 연산을 진행해야 한다는 걸 확인한 후 코드를 고쳤다.

 

 

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

[백준] 1912번: 연속 합 [C#]  (0) 2024.04.27
[백준] 2748번: 피보나치 수 2 [C#]  (0) 2024.04.26
[백준] 11659번: 구간 합 구하기 4 [Java]  (0) 2024.04.24
[백준] 1149번: RGB거리 [C#]  (0) 2024.04.17
[백준] 9095번: 1, 2, 3 더하기 [C#]  (0) 2024.04.16
다이나믹 프로그래밍 한접시/ [백준] 11659번: 구간 합 구하기 4 [Java]
2024-04-24 21:40:00

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
 
public class Main {
    public static void main(String[] args) throws IOException 
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] input = br.readLine().split(" ");
 
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        
        String[] num = br.readLine().split(" ");
        int[] nums = new int[N];
        for (int i =0; i < N; i++)
            nums[i] = Integer.parseInt(num[i]);
        
        int[] dp = new int[N+1];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++)
            dp[i] = dp[i - 1] + nums[i - 1];
        
        for (int j = 0; j < M; j++)
        {
 
            
            String[] line = br.readLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);
        
            
            System.out.println(dp[b] - dp[a - 1]);
        }
        
        
    }
}
 
 cs

 

입력되는 값이 워낙 많아서 그런지 알고리즘 자체는 맞았는데, 계속 시간 초과가 났었다.

입출력의 시간을 줄여주는 방법을 사용해서 출ㄹ겨해 주었다.

 

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

[백준] 2748번: 피보나치 수 2 [C#]  (0) 2024.04.26
[백준] 1932번: 정수 삼각형 [C#]  (1) 2024.04.25
[백준] 1149번: RGB거리 [C#]  (0) 2024.04.17
[백준] 9095번: 1, 2, 3 더하기 [C#]  (0) 2024.04.16
[백준] 1463번: 1로 만들기 [C#]  (0) 2024.04.15
하루 한 접시/ [백준] 1747번: 소수&팰린드롬 [C#]
2024-04-23 22:12:29

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
62
63
64
65
66
67
68
69
70
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());
 
            _1747_boj boj = new _1747_boj();
 
            boj.boj_1747();
 
        }
    }        
    internal class _1747_boj
    {
        public int[] prime = new int[1_000_001];
        public int[] pal = new int[1_000_001];
        public List<int> res = new List<int>();
 
        public void boj_1747()
        {
            int input = int.Parse(Console.ReadLine());
 
            while (true)
            {
                if (is_prime(input))
                    if (is_pal(input.ToString()))
                    {
                        res.Add(input);
                        break;
                    }
                input++;
            }
            Console.WriteLine(res[0]);
 
        }
        public bool is_prime(int num)
        {
            if (num == 1)
                return false;
            else if (num <= 3)
                return true;
            for (int j = 2; j <= Math.Sqrt(num); j++)
            {
                if (num % j == 0)
                    return false;
            }
            return true;
        }
        public bool is_pal(string num)
        {
            for (int i = 0; i < num.Length / 2; i++)
            {
                if (num[i] != num[num.Length - i - 1])
                    return false;
            }
            return true;
        }
    }
}
 
 cs

왜 틀렸는지 함참을 고민하고있었는데, 문제를 다시 읽어보니 ''''같거나'''' 큰 값을 구하라는 거였다....

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

[백준] 1924번: 2007년 [C#]  (0) 2024.05.07
[백준] 2816번: 디지털 티비 [C#]  (0) 2024.05.06
[백준] 1100번: 하얀 칸 [Python]  (0) 2024.04.22
[백준] 1158번: 요세푸스 문제 [C#]  (0) 2024.04.20
[백준] 10872번: 팩토리얼 [Python]  (0) 2024.04.12
하루 한 접시/ [백준] 1100번: 하얀 칸 [Python]
2024-04-22 22:55:59

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
if __name__ == "__main__":
    cnt = 0
    for i in range(0, 8):
        line = input()
        for j in range(0, 8):
            if i % 2 != 0 and j % 2 != 0 and line[j] == 'F':
                cnt+= 1
            elif i % 2 == 0 and j % 2 == 0 and line[j] == 'F':
                cnt+=1
 
    print(cnt)
 
 
 cs

 

홀수열의 홀수칸에 F가 있다면 1증가, 짝수열의 짝수칸에 F가 있다면 1증가

마지막에 횟수 출력

 

 

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

[백준] 2816번: 디지털 티비 [C#]  (0) 2024.05.06
[백준] 1747번: 소수&팰린드롬 [C#]  (0) 2024.04.23
[백준] 1158번: 요세푸스 문제 [C#]  (0) 2024.04.20
[백준] 10872번: 팩토리얼 [Python]  (0) 2024.04.12
[백준] 1092번: 배 [C#]  (0) 2024.04.05
카테고리 없음/ [백준] 1406번: 에디터 [C#][푸는 중...]
2024-04-21 23:59: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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
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());
            _1406_boj boj = new _1406_boj();
 
            boj.boj_1406();
 
        }
    }
        public class Node
    {
        public char data;
        public Node link = null;
    }
    internal class _1406_boj
    {
        public static Node head = null;
        public StringBuilder sb = new StringBuilder();
        public void boj_1406()
        {
            string input = Console.ReadLine();
            for (int i =0; i < input.Length; i++)
            {
                make_node(input[i]);
            }
            make_node('C');
            print_node(head);
            int cnt = int.Parse(Console.ReadLine());
            for (int i = 0; i < cnt; i++)
            {
                string input2 = Console.ReadLine();
                switch(input2[0])
                {
                    case 'P':
                        insert_node(input2[2]);
                        break;
                    case 'L':
                        move_left();
                        break;
                    case 'D':
                        move_right();
                        break;
                    case 'B':
                        delete_node();
                        break;
                }
                print_node(head);
            }
        }
        public void make_node(char data)
        {
            Node node = new Node();
            node.data = data;
            if (head == null)
            {
                head = node;
                return;
            }
 
            Node current = head;
            while (current.link != null)
                current = current.link;
            current.link = node;
 
        }
        public void print_node(Node start)
        {
            if (head == null)
                return;
            if (start.data != 'C')
                sb.Append(start.data);
            while (start.link != null)
            {
                start = start.link;
                if (start.data != 'C')
                    sb.Append(start.data);
 
            }
            Console.WriteLine(sb);
            sb.Clear();
        }
        public void insert_node(char insert_data)
        {
            Node node = new Node();
            node.data = insert_data;
 
            if (head.data == 'C')
            {
                node.link = head;
                head = node;
            }
 
 
            Node current = head;
            while (current.link != null)
            {
                Node pre = current;
                current = current.link;
                if (current.data == 'C')
                {
                    pre.link = node;
                    node.link = current;
                }
            }
        }
        public void move_left()
        {
            Node current = head;
            Node node = new Node();
            node.data = 'C';
            if (head.data == 'C')
            {
                return;
            }
            if (head.link.data == 'C')
            {
                node.link = head;
                head.link = head.link.link;
                head = node;
                return;
            }
 
            while (current.link != null)
            {
                Node pre = current;
                current = current.link;
                if (current.link.data == 'C')
                {
 
                    node.link = current;
                    pre.link = node;
                    if (current.link.link == null)
                        current.link = null;
                    else
                        current.link = current.link.link;
                    return;
                }
 
            }
        }
        public void move_right()
        {
            Node current = head;
            Node node = new Node();
            node.data = 'C';
            if (head.data == 'C')
            {
                head = head.link;
                node.link = head.link;
                head.link = node;
                current.link = null;
                return;
            }
            while (current.link != null)
            {
                Node pre = current;
                current = current.link;
 
                if (current.data == 'C')
                {
                    if (current.link == null)
                        return;
                    else
                    {
                        pre.link = current.link;
                        node.link = current.link.link;
                        current.link.link = node;
                        current.link = null;
                        return;
                    }
                }
 
            }
        }
        public void delete_node()
        {
            Node current = head;
            if (head.data == 'C')
                return;
            while (current.link != null)
            {
                Node pre = current;
                current = current.link;
                if (current.data == 'C')
                {
                    if (pre == head)
                    {
                        pre.link = null;
                        head = current;
                        return;
                    }
                    pre.link = current.link;
                    current.link = null;
                    pre.data = 'C';
                    return;
                }
            }
        }
    }
}
 
 cs

시간초과가 계속 뜬다... 다른 방법을 찾아봐야겠지?

하루 한 접시/ [백준] 1158번: 요세푸스 문제 [C#]
2024-04-20 23:54:50

 

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
62
63
64
65
66
67
68
69
70
71
72
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace 연습장
{
    public class _1158_boj
    {
        public static Node head;
        public void boj_1158()
        {
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int num = arr[0];
            int idx = arr[1];
 
            for (int i = 1; i <= num; i++)
            {
                Node node = new Node();
                node.data = i;
 
                if (head == null)
                {
                    node.link = node;
                    head = node;
                    continue;
                }
                Node current1 = head;
                while (current1.link != head)
                {
                    current1 = current1.link;
                }
 
                current1.link = node;
                node.link = head;
            }
 
            List<int> arr2 = new List<int>();
 
            Node current = head;
            Node pre = current;
            while (current.link != current)
            {
                for (int i = 1; i < idx; i++)
                {
                    pre = current;
                    current = current.link;
                }
                arr2.Add(current.data);
                pre.link = current.link;
                current = current.link;
            }
            arr2.Add(current.data);
 
            Console.Write('<');
            for (int i = 0; i < num; i++)
            {
                Console.Write(arr2[i]);
                if (i != num - 1)
                    Console.Write(", ");
            }
            Console.WriteLine('>');
        }
    }
    public class Node
    {
        public int data;
        public Node link;
    }
}
 
 cs

 

원형 리스트의 값을 하나씩 추출해서 출력해주면 되는 문제이다. 처음에는 파이썬을 사용해서 구현하려 했는데, 계속 런타임 에러가 나길래 C#으로구현을 해줬다.

 

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

[백준] 1747번: 소수&팰린드롬 [C#]  (0) 2024.04.23
[백준] 1100번: 하얀 칸 [Python]  (0) 2024.04.22
[백준] 10872번: 팩토리얼 [Python]  (0) 2024.04.12
[백준] 1092번: 배 [C#]  (0) 2024.04.05
[백준] 18258번: 큐 2 [C#]  (0) 2024.04.03
배열 한접시/ [백준] 1919번 애너그램 만들기 [Java]
2024-04-19 21:39:16

 

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
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String arr1 = sc.nextLine();
        String arr2 = sc.nextLine();
 
        int[] alpha = new int[26];
        
        for (int i =0; i < arr1.length(); i++)
            alpha[arr1.charAt(i) - 'a']++;
        for (int i =0; i < arr2.length(); i++)
            alpha[arr2.charAt(i) - 'a']--;
        
        int res = 0;
        
        for (int i =0; i < 26; i++)
        {
            res += Math.abs(alpha[i]);
        }
        
        System.out.println(res);
        
    }
}
 
 cs

 

 

 

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

[백준] 11328번: StrFry [Java]  (0) 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
배열 한접시/ [백준] 11328번: StrFry [Java]
2024-04-19 18:50:14

 

 

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");
        }
    }
}
 
 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
배열 한접시/ [백준] 13300번: 방 배정 [Java]
2024-04-19 17:30:52

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);
    }
}
 
 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
배열 한접시/ [백준] 두 수의 합 [C#]
2024-04-19 00:27:16

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);
        }
 
    }
}
 
 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

티스토리툴바