6개의 댓글이 있습니다.
-
-
Taeyoon_Lee -
우왕ㅋ 좋은 방법이네요~
17년 전 link
-
-
-
JongMan -
하드에서 더 좋은 방법은, 에디토리얼에도 나온 방법이지만, 두 가지 경우로 나눠 푸는 것인 것 같아요.
1. 주어진 숫자를 A 라고 할 때, A < B 에 대해서 count(A) == count(B) 인 경우
a. A 와 B 가 첫 자리에서 달라질 때: B 의 해당 자리 수는 A 의 해당 자리수보다 커야 합니다.
b. A 와 B 가 두번째 자리에서 달라질 때: B 의 해당 자리 수는 A 의 해당 자리수보다 커야 합니다.
c.
d. ...
2. B < A 인 경우: 99999...9 를 지나 wraparound 한 경우죠.
두 경우 모두, smallest[i][j] = i개의 segment 를 가지고 만들 수 있는 j자리의 수 중 가장 작은 것은? 이라는 점화식을 풀면 쉽게 풀 수 있죠. 'X 보다 lexicographically larger 중 가장 작은 것 구하기' 스타일의 문제를 풀 수 있는 일반적 패턴인데.. 'X 와 Y 가 달라지는 첫 번째 위치' 를 찾는거죠. 그 전은 X 와 똑같아야 하고, 그 이후는 가능한 가장 작은 수일 테니까요.
17년 전 link
-
-
-
astein -
음.. 제가 연습할 때 푼 방법도 위에서 JM님이 설명해 주신 방법과 완전히 같네요 :$
wraparound인 경우는 첫번째 댓글에 달아뒀던 것처럼 string의 앞에 "2"를 붙여주면 해결이 되고요.
" smallest[i][j] = i개의 segment, j자리의 수 중 가장 작은 것은? " 이라는 문제는 greedy 로 해결 가능한 문제입니다.
k 자리의 digit을 채우는 segment는 최소 2k개, 최대 7k개임을 알 수 있기 때문이죠. 앞자리를 0 ~ 9 까지 채워넣어가면서,
k-1 자리의 digit에서 사용할 수 있는 segment가 2(k-1)이상, 7(k-1)이하인 경우는 앞자리를 고정시킬 수 있으니까요 :3
17년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Taeyoon_Lee
11등한 기념으로(형들이 쓰래서) 에디토리얼을 써보겠습니다.
250, 500, 1000으로 구성된 set이었는데, 그럭저럭 알맞은(?) 난이도였다고 생각합니다.
예상외의 인물이 1등을 했는데, 저도 1등 한번 해보고 싶어요.(?)
Easy (250 pts.)
문제 설명
n*m 격자로 나뉘어져 있는 나무판이 있습니다.
250답게 brute force로 해결할 수 있습니다.
각 격자는 검정(B)색이나 흰(W)색이 칠해져 있습니다.
우리는 8*8 크기로 나무판을 잘라서 체스판을 만들 것입니다.
체스판은 인접한 모든 격자가 서로 다른 색이어야 합니다.
그래서 나무판을 자른 후에, 각 격자에 색칠을 다시해야 하는데,
색칠해야 되는 칸이 최소가 되도록 자르면, 몇 칸을 색칠하면 될까요?
가능한 체스판은 아래와 같이 두종류가 있습니다.
~~~ text
WBWBWBWB
BWBWBWBW
BWBWBWBW WBWBWBWB
WBWBWBWB BWBWBWBW
BWBWBWBW WBWBWBWB
WBWBWBWB BWBWBWBW
BWBWBWBW WBWBWBWB
WBWBWBWB BWBWBWBW
BWBWBWBW WBWBWBWB
~~~
두가지 판을 가능한 모든 위치에 대응해보면서
처음 칠해진 칸과 다른 칸의 개수를 세어보면 됩니다.
~~~ cpp
#define FOR(i,a,b) for( int i=(a); i<(b); ++i) dt) {
#define REP(i,n) for(int i=0; i<(n); ++i)
#define SZ(X) (int)(X).size()
class RepaintTheChessboard {
public:
int minimumChanges(vector
int n=SZ(dt),m=SZ(dt[0]);
int dp=234234234;
REP(i,n-8+1) {
REP(j,m-8+1) {
int su=0;
FOR(y,i,i+8)
FOR(x,j,j+8) {
if ((y+x)%2==0 && dt[y][x]=='W') su++;
if ((y+x)%2==1 && dt[y][x]=='B') su++;
}
dp=min(dp,su);
dp=min(dp,64-su);
}
}
return dp;
}
};
그리고 위 아래에서 숫자를 하나씩 처리합니다. (답에 누적시킵니다.)
~~~ text
123
124
.
.
129
130
131
.
.
448
449
450
451
452
.
.
~~~
시작 숫자의 1의 자리가 0이면 계산을 잠시 멈추고,
마지막 숫자의 1의 자리가 9면 역시 계산을 잠시 멈춥니다.
그리고 위에서부터 숫자를 10개씩 묶어 볼게요.
0으로 시작해서 9로 끝나니까, 딱 맞게 묶이겠죠?
그러면 우선 1의 자리부터 처리합시다.
~~~ text
130
131
.
.
448
449
~~~
0~9가 각각 (44-13+1)개가 있습니다. 계산하시구요.
1의 자리를 처리하고나면, 문제는
13부터 44까지 등장하는 각각의 디지트를 세는 문제로 바뀝니다.
물론 곱하기 10을 해서 답을 구해야 겠죠?
~~~ cpp
typedef vector VI; getCounts(int N) {
#define REP(i,n) for(int i=0; i<(n); ++i)
VI dp;
void ret(int ka,int kb)
{
while (ka>0) {
dp[ka%10]+=kb;
ka/=10;
}
}
class PageNumbers {
public:
vector
int a=1,b=N,c=1;
dp = VI(10,0);
while (a<=b) {
while (a%10>0 && a<=b)
ret(a++,c);
if (a>b)
break;
while (b%10>0 && a<b)
ret(b--,c);
REP(i,10)
dp[i]+=(b/10-a/10)*c;
ret(b--,c);
a/=10;
b/=10;
c*=10;
}
return dp;
}
};
이걸 구해놓으면 뒷자리부터 하나씩 올려가면서
계산을 해볼 수 있습니다.
예를 들어 현재 숫자가 123456이라고 하면
끝에 6을 7, 8, 9로 하나씩 바꿔가면서 가능 여부를 검사합니다.
6을 쓰는데 이용되는 선분의 수가 6이니까
dy[1][6][7], dy[1][6][8], dy[1][6][9] 중에 1이 있나 검사를 해보고, 있으면 그렇게 바꾸면 됩니다.
하지만 아쉽게도 전부 1이 아닙니다.
그러면 다음 자리로 옮겨와서 5를 하나씩 올려봅니다.
56을 쓰는데 이용된 선분의 수는 11개니까
dy[2][11][6], dy[2][11][7], dy[2][11][8], dy[2][11][9]를 찾아보겠죠.
dy[2][11][6]이 1이겠네요. 그럼 5를 6으로 바꿔주고,
그 뒷자리는 무조건 가능한 가장 작은 수로 써줍니다. 역시 dy배열을 참고해서 해야 겠죠?
dy[1][5][2]가 1일 테니, 처음에 "56"이었던 숫자가 "62"로 바뀌면 되겠군요.
~~~ cpp
#define FOR(i,a,b) for( int i=(a); i<(b); ++i)
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FORD(i,a,b) for( int i=(a); i>(b); --i)
// dt[0,n-1] 에 각 자리의 숫자가 들어가 있습니다.
FORD(i,n-1,-1) {
int bu,sum;
bu=dt[i];
sum=0;
FOR(j,i,n) sum+=su[dt[j]]; // 바꿀 숫자들의 선분 합을 구합니다.
while (dt[i]<9) { // 9일 때까지 바꿔 봅니다.
dt[i]++;
if (dy[n-i][sum][dt[i]]) { // 가능하다면, 그렇게 써주고
sum-=su[dt[i]];
i++;
while (i<n) { // 뒷자리는 가능한 제일 작은 수로 채웁니다.
REP(j,10)
if (dy[n-i][sum][j]) {
sum-=su[j];
dt[i]=j;
break;
}
i++;
}
// 현재 바뀐 숫자에서 원래 숫자를 빼서 답을 구합니다.
// 생략했습니다.
return ret;
}
}
dt[i]=bu; // 9일 때까지 바꿔 보았는데, 가능한 경우가 없으면 그냥 다시 돌려 놓습니다.
}
17년 전