https://www.acmicpc.net/problem/14391
문제 어렵다!
최소 4개의 경우의 수부터 16까지 경우의 수가 있는걸 대체 어떤수로 풀란 말이냐 ㅠㅠㅠㅠㅠㅠ
처음에는
"어차피 최대가 나오는 것은 4자리 수의 합이니 가로 , 세로 따로 구해서 max 해주면되지않을까?" 라 생각 해서 그렇게 풀었더니
세상이 그렇게 쉽지가 않더군요
결국 검색
아하!
이 문제는 "비트마스크"를 생각해내지 못하면 풀기 어려운 문제였던 것이다...
이게 무슨뜻이냐
각 모든 index에 대해서 0과1을 정해준 후, 0은 세로값만 1은 가로값이라 생각하고 이어진 1들의 수 + 이어진 0들의 수를 더한 것이였다.
이게 무슨뜻인고 하니
예를들어 이런 2*2 형태의 직사각형과 각 숫자를 5 8 9 6 을 넣었다고 쳤을 때
앞서 말한 랜덤 0 과 1을 이렇게 넣어줬다고 해보자
이때 우리는 0을 세로 1을 가로값이라 해줬으니
저런 식으로 한 묶음을 숫자 하나로 보는것이다
만약 가로나 세로가 1개밖에 없다면 그것은 1*1 숫자 하나만 되는 것이다.
"어 근데 만약 4*4일경우 인덱스가 16개고 그럼 총 2^16개의 경우의수가 나오는 건가요?"
ㅇㅇ
맞다
이제 코드를 보여주겟다
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int arr[n][m];
bool b[n][m];
long long best=-9999999999;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
{
for (int j = 0; j < m; j++)
arr[i][j] = s[j] - '0';
}
}
for (int mask = 0; mask < (1 << n * m); mask++)
{
long long sum = 0;
for (int i = 0; i < n; i++)
{
int cur = 0;
for (int j = 0; j < m; j++)
{
int id = i * m + j;
if ((mask & (1 << id)) == 0)
cur = cur * 10 + arr[i][j];
else
{
sum += cur;
cur = 0;
}
}
sum += cur;
}
for (int i = 0; i < m; i++)
{
int cur = 0;
for (int j = 0; j < n; j++)
{
int id = j * m + i;
if ((mask & (1 << id)))
cur = cur * 10 + arr[j][i];
else
{
sum += cur;
cur = 0;
}
}
sum += cur;
}
best = max(best, sum);
}
cout << best << "\n";
}
세상엔 참 똑똑한 사람들이 많은 것 같다.
for (int mask = 0; mask < (1 << n * m); mask++)
해당 코드는 mask된 인덱스를 보여주는 코드인데
난 이걸 왜 생각을 못했을까 ㅠㅠ
1<<n*m은 2^(n*m)을 나타내고
mask를 2진수로 표현을 해보면
0000,,,,0 이때부터시작해서
1111....1 까지 모든 경우의수를 표현하게 되는 것이다
그럼 이걸 그냥 2차원 인덱스를 한줄로 세운거라 생각하면
모든 인덱스에 마스크를 씌우는 경우의 수인 것이다!!
long long sum = 0;
for (int i = 0; i < n; i++)
{
int cur = 0;
for (int j = 0; j < m; j++)
{
int id = i * m + j;
if ((mask & (1 << id)) == 0)
cur = cur * 10 + arr[i][j];
else
{
sum += cur;
cur = 0;
}
}
sum += cur;
}
각각 코드는 가로와 세로를 나타내는 표현이다
위에 보여준 예시는 0이 세로지만 여기선 0을 가로 1을 세로로 표현하겠다
mask & (1<<id) == 0 이라는 표현은 다들 알겠지만
id는 어떤 인덱스인지 보여준다. 예를들어 2*2에서 0110 으로 인덱싱이 되었을때, [0][1]인덱스의 위치는 0*2+1=1 이고 이는 0001이다.
이걸 and 연산을 했을 때
0110과 0001은 겹치는게 없으니 0이 나오고 그렇다면 마스킹 된 값이 0인 것으로 가로값이다
이게 무슨소리냐고?
마스킹은 0110으로 되어있다는 뜻은 2번째 인덱스와 3번째 인덱스가 마스킹 되었다는 뜻을 의미한다.
그렇다면 id=0일때를 볼까? i=0이고 j=0일때는
1<<0은 몇? = 1
즉
0001 이라는 뜻이고, 이건 0번째 인덱스가 1인가?를 묻는것이다.
근데 아니잖아? 그니까0
그럼 두번째로 가보자 id=1이야
그럼 i<<1 ==2
10
0110과 &하면 1 왜 ? 1이니까!
그래서 애는 세로값인것이다~
여기는 당장 가로값만 계산하고있으니, 중간에 합을 멈추고, cur을 0으로 해준후 다시 처음부터 시작한다.
가로세로 전부 한 이후에 max를 구해서 답을제출!
어렵다
2번3번꼬아서 생각해야됨..
