문제 URL : https://www.acmicpc.net/problem/17830
17830번: 이진수씨의 하루 일과
이진수 씨는 이진수를 사랑한다. 그의 하루 일과는 하루 종일 이진수 두 개를 생각해놓고, 그 두 수의 곱을 "오늘의 이진수"로 선정한다. 그리고 예쁜 종이를 한 장 사와 "오늘의 이진수"를 적은 �
www.acmicpc.net
문제 접근법 :
n개의 길이 string을 입력받아 n개의 연속된 1과 입력받은 string을 곱해서 최대값과 최솟값을 만드는건데
당연히 최댓값은 ?를 전부 1로 바꿔주면되고 최솟값은 ?를 전부 0으로 바꿔주면 되서 곱하면 된다고 생각하는게 일반적이라고 생각했습니다.
그러나 최대자리숫자와 최소자리숫자로 만들고 이걸 그냥 곱하는 알고리즘을 짜게되면 100% 시간초과 이기때문에 다른방법을 찾아야 했습니다.
그래서 다 곱해봐서 규칙을 찾아냈습니다.
우선 결과를 얘기하자면 n개의 연속된 길이와 n개의 길이가 n개의 n자리수라고 생각하면 오산이라는겁니다.
예를들면 6과 6개의 길이인 string을 입력을받을때
아래 그림처럼
6자리수 x 4자리수로 생각해야한다 오른쪽숫자의 앞 00은 없는수라고 생각하면 쉽다
그리고 이걸 1~ 111111까지 곱해본결과 그 해답을 찾았다
N자리수 일때 1이 한개있을 때는 1뒤에 있는 0을 갖다 붙여주면 되기 때문에 N-1을 더하면된다
2개 이상일때는 입력받은 n과 N자리수를 더해주면 된다는것이다.
즉 1이 한개 있을대와 2개이상있을대의 차이는 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
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
|
#include <iostream>
#include<cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include<deque>
using namespace std;
int maxstring(int n,string &s)//자릿수 최대로 만드는 함수
{
int oneidx = -1;
int cnt1 = 0;
for (int i = 0; i < s.size(); i++)
{
if (oneidx == -1&&(s[i]=='1'||s[i]=='?'))
{
oneidx = s.size() - i;
cnt1++;
continue;
}
if (s[i] == '1' || s[i] == '?')//?표는 무조껀 1로바꾼다고 생각하면됨
cnt1++;
}
if (cnt1 == 0)
return 1;//1이아무것도 없으니 그냥 곱해봤자 0이될테니 사이즈를 출력하는거니까 1
else if (cnt1 == 1)//1이 한개밖에없다는 뜻임 결국 뒤에 0만채우는꼴
return n + oneidx - 1;
return n+oneidx;//여긴 cnt1 이 2개이상이라는뜻이지만 1의 맨앞자리 자릿수와 더해주면 끝
}
int minstring(int n, string &s)//자릿수 최대로 만드는 함수
{
int oneidx = -1;
int cnt1 = 0;
for (int i = 0; i < s.size(); i++)
{
if (oneidx == -1 && (s[i] == '1' ))
{
oneidx = s.size() - i;
cnt1++;
continue;
}
if (s[i] == '1')//?표는 필요없음 전부 0이라고 생각하면됨
cnt1++;
}
if (cnt1 == 0)
return 1;//1이아무것도 없으니 그냥 곱해봤자 0이될테니
else if (cnt1 == 1)//1이 한개밖에없다는 뜻임 결국 뒤에 0만채우는꼴
return n + oneidx - 1;
return n + oneidx;//여긴 cnt1 이 2개이상이라는뜻이지만 1의 맨앞자리 자릿수와 더해주면 끝
}
void solve(int n, string &s)
{
cout << maxstring(n, s) <<" "<<minstring(n,s)<<"\n";
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test;
cin >> test;
while (test--)
{
int n;
string s;
cin>>n >> s;
solve(n, s);
}
}
|
cs |
궁금한점 또는 모르는것이 있다면 언제든지 댓글을 달아주시길 부탁드립니다.
성의껏 답변 드리겠습니다.
n자리수를 만들어서 전부 곱한 소스코드입니다.
굉장히 느린 알고리즘이에요 입력은 10 정도까지만 입력받아보고 그결과들을 눈으로 한번 직접보시는것도
좋은 공부가 될겁니다.
(사실 일일이 n자리수 결과들을 그림으로 그리기 귀찮아서 코드를 만들어서 그결과들을 직접 컴퓨터로 계산시킨것은 안비밀 ㅋㅋㅋㅋ)
|
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
|
#include <iostream>
#include<cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include<deque>
#include <stack>
using namespace std;
string add(string a, string b)
{
int asize = a.size();
int bsize = b.size();
string longstr, shortstr;//문자길이가 다를수도있으니까 맞춰줘야함
if (asize > bsize)
{
longstr = a;
shortstr = b;
}
else
{
longstr = b;
shortstr = a;
}
if (asize != bsize)
{
int gap = longstr.size() - shortstr.size();
for (int i = 0; i < gap; i++)
shortstr = '0' + shortstr;
}
string result = "";
char c = 0;
char carry = 0;
for (int i = longstr.size() - 1; i >= 0; i--)
{
c = longstr[i] + shortstr[i] - '0' + carry;
if (c > '1'){
c -= 2;
carry = 1;
}
else
carry = 0;
result = c + result;
}
if (carry)
result = '1' + result;
return result;
}
string mul(int n, string s)
{
string one, result = "";
for (int i = 0; i < n; i++){
one += '1';
}
int t = 0;
for (int i = n - 1; i >= 0; i--)
{
string yebi = one;
if (s[i] == '1')
{
for (int j = 0; j < t; j++)
{
yebi += '0';
}
}
else{
yebi = '0';
}
result = add(result, yebi);
t++;
}
return result;
}
int main(void)
{
int n;
cout << "만들고 싶은 자리수 입력: " ;
cin >> n;
for (int i = 1; i <= n; i++)
{
stack<int> st;
string s;
int temp = (1<<i)-1;
while (temp)
{
st.push(temp % 2);
temp /= 2;
}
while (!st.empty())
{
s += to_string(st.top());
st.pop();
}
for (int j = 1; j <= (1<<i)-1; j++)
{
int temp2 = j;
string s2;
for (int k = 0; k < i; k++)
{
st.push(temp2 % 2);
temp2 /= 2;
}
while (!st.empty())
{
s2 += to_string(st.top());
st.pop();
}
string s3 = mul(i, s2);
cout << i << "자리수 " << s << " x " << s2 << "=" << s3<<" ->길이 : "<<s3.size() << endl;
}
cout << endl;
}
}
|
cs |
'백준' 카테고리의 다른 글
| 백준 2812 크게만들기 (0) | 2020.07.22 |
|---|---|
| 백준 1890 점프 (0) | 2020.07.22 |
| 백준 2630 색종이 만들기 (0) | 2020.07.20 |
| 백준 5427 불 (0) | 2020.07.20 |
| 백준 1992 쿼드트리 (0) | 2020.07.20 |
