먼저 그리디 알고리즘을 알아보았다.
지금 할 수 있는 단계에서 최선의 해결책을 얻는 알고리즘이라고 한다.
동전 나누는게 예로 많이 나왔는데
만약 560원이 있다면 가장 적은 동전 갯수인
500원짜리 1개 50원짜리 1개 10원짜리 1개로 나눌 수 있고
이게 그리디 알고리즘을 적용하여 그때그때 최선의 결과로 나타내는 것이라고 한다.
여기 문제에 적용하면 먼저 보드를 4로 나눠서 4의 배수인지 확인해보고 A를 채우고
아니라면 4로 나눈 나머지가 2의 배수인지 확인해서 2의 배수라면 A를 먼저 채운다음 B를 채우면 되는 것이고
2의 배수도 아니라면 -1을 출력해주면 되는 것 같았다.
입력되는 문자열을 .을 기준으로 나누고 A랑 B를 X개수만큼 각각 잘 대체했다
.을 도대체 어떻게 나타낼까 엄청 고민하다가 substring으로 입력된 문자열을 하나하나 나눈 다음 리스트에 넣고
A와 B로 대체한 것을 넣은 리스트를 또 만들고
둘이 비교해서 .을 나타내주면 되겠다고 생각했는데..
비교할때마다 자꾸 인덱스 범위 버그가 나서 두 리스트를 어떻게 비교해야하나 엄청 해멨다.
count 하나만 있으면 되는건데 그게 생각이 안나서 제일 헤맴ㅠㅠ
마지막으로 . 만 찍었을 경우를 생각안해서 자꾸 틀렸다고 나오는 바람에 3트까지 갔다
처음 문자열을 나눌때 X가 포함되지 않는 경우를 만들어서 해결ㅠㅠ
|
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
|
using System;
using System.Collections.Generic;
using System.Linq;
using System.Net.NetworkInformation;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;
namespace _1343
{
class Program
{
static void Main(string[] args)
{
string input = Console.ReadLine();
List<string> inputDV = input.Split('.').ToList();
List<string> inputList = new List<string>();
List<string> temp = new List<string>();
bool isPrint = false;
for (int i=0; i<input.Length; i++)
{
inputList.Add(input.Substring(i, 1));
if(!inputList[i].Contains("X"))
{
isPrint = true;
}
}
for(int i=0; i<inputDV.Count; i++)
{
if(inputDV[i].Length%4==0)
{
for(int j=0; j<inputDV[i].Length; j++)
{
var a = inputDV[i].Substring(j, 1);
a = "A";
temp.Add(a);
isPrint = true;
}
}
if(inputDV[i].Length % 4 != 0)
{
if (inputDV[i].Length % 4 % 2 != 0)
{
Console.WriteLine(-1);
isPrint = false;
break;
}
else if (inputDV[i].Length % 4 % 2 == 0)
{
for (int j = 0; j < inputDV[i].Length - inputDV[i].Length % 4; j++)
{
var a = inputDV[i].Substring(j, 1);
a = "A";
temp.Add(a);
isPrint = true;
}
for (int j = inputDV[i].Length - inputDV[i].Length % 4; j < inputDV[i].Length; j++)
{
var b = inputDV[i].Substring(j, 1);
b = "B";
temp.Add(b);
isPrint = true;
}
}
}
}
if(isPrint)
{
int count = 0;
for (int i=0; i<inputList.Count; i++)
{
if(inputList[i]!=".")
{
inputList[i] = temp[count];
count++;
}
}
foreach (var data in inputList)
{
Console.Write(data);
}
}
}
}
}
|
그리디 알고리즘 참고
(Algorithm) 탐욕(그리디) 알고리즘(greedy algorithm) - 활동 선택 문제, 분할 가능 배낭 문제
안녕하세요. 이번 시간에는 그리디 알고리즘에 대해 알아보겠습니다. 그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘입니다. 동적 프
www.zerocho.com
1343번: 폴리오미노
첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.
www.acmicpc.net
'C# > 알고리즘' 카테고리의 다른 글
| 10. 10845번 큐 (해결) (0) | 2020.06.21 |
|---|---|
| 9. 1302번 베스트셀러 (LINQ group by) (0) | 2020.06.07 |
| 7. 1181번 단어정렬(수정) (0) | 2020.05.24 |
| 6. 2884번 알람시계 (0) | 2020.04.26 |
| 5. 14681번 사분면 고르기 (0) | 2020.04.26 |