<BOJ 2248 이진수 찾기> 문제와 비슷한 다이나믹 프로그래밍 문제이다.
a1<=a2<=a3<=...<=aN이면서 a1+a2+a3+...+aN==M을 만족하는 수열 중 사전 순으로 k번째 수열을 구하는 문제인데, 막연하다. 어려워 보인다. 일단 문제의 조건을 만족하는 수열 aN의 합이 M인 경우의 수를 구하는 것은 좀 더 나아 보인다.
d[val][sum][idx] = 수열 val이상 값 부터 사용해서(이전 값들은 val이하의 값들) 남은 sum을 만드는 경우의 수, idx는 사용하는 수열의 인덱스(길이를 나타내는 것으로 봐도 됨)
로 놓으면 d[val][sum][idx]=SUM(a[idx]=val이상의 수, d[a[idx]][sum-a[idx]][idx+1] ) 가 될 것 같다. 이렇게 경우의 수를 구했다면, k를 가지고 d[1][sum], d[2][sum]... 들이 저장하고 있는 개수와 비교를 해서 그 때 그 때 해당하는 a[idx]를 출력하면 k번째 수열을 알 수 있을 것이다.
구현해 보려고 하는데, 배열의 크기에서 a[idx]값을 어디까지 잡아야 하는지 잠깐 고민했다. sum값까지 즉 최대 M으로 잡으면 된다! M을 넘을 수는 없기 때문에...
일단 우여곡절 끝에 AC를 받긴 했는데... 자고 일어나서 다시 한 번 보고 다시 풀어봐야겠다.
그리고 다른 사람들 풀이도 봐서 연습하자. 좀 까다롭다.
2016년 10월 7일 금요일
2016년 10월 6일 목요일
BOJ 9455 박스
이 문제는 엄청 쉬워보이지만 나에게는 쉽지 않았다... 처음에는 예제마나 보고 제일 위에 있는 박스와 제일 아래있는 박스의 차이 만으로 구했는데, 예제만 될 뿐이다. 잘 생각해보니 박스 하나 하나가 얼마나 움직이는지를 봐야할 것 같았다. 그리고 그 하나 하나를 볼 때도 제일 아래 박스 부터 보면서 누적되는 박스의 수를 count해 놓으면 박스 하나 하나를 볼 대마다 박스 아래에 몇 개의 박스가 있는지를 알 수 있고, 그 사실과 현재 박스의 위치를 비교해서 각 박스가 몇 칸을 움직일 수 있는지 계산할 수 있다.
코드도 짧고, 문제도 쉬워 보이지만 예제만 보고 방심했다가는 충분히 틀릴 수 있을 것 같다.
코드도 짧고, 문제도 쉬워 보이지만 예제만 보고 방심했다가는 충분히 틀릴 수 있을 것 같다.
BOJ 2494 숫자 맞추기
회전 가능한 숫자 나사 N개가 아래위로 연결 되어 있는데, 숫자 나사는 각각 10개의 면을 가지고 있고 숫자가 0~9까지 순서대로 적혀있다. 왼쪽이나 오른쪽으로 돌릴 수 있는데, 왼쪽으로 돌릴 경우 자신의 밑에 있는 모든 숫자 나사들도 같이 돌아간다. 하지만 오른쪽으로 돌릴 경우 자신만 돌아간다. 이 때 현재 상태와 원하는 상태가 주어지면 원하는 상태로 만들기 위해 최소 몇 칸을 돌려야 하는지, 그리고 어떤 숫자 나사를 몇 칸 움직였는지도 구하는 문제이다.
일단 최소 몇 칸을 돌려야 하는지에 대해 먼저 생각해보자.
처음에는 위에 것을 우선적으로 최대한 많이 돌려야 하나? 우선적으로 어떤 것을 돌리는 게 최소가 될까..? 라든지 .. 좀 찾아보려 했지만 찾지 못했고, 일단 모든 경우를 다 해본다고 하면 각 숫자 나사마다 왼쪽으로 9칸 오른쪽으로 9칸까지... 안 움직이는 경우까지 포함해서 20가지 경우가 있을 것이다. 그런데 숫자 나사의 개수가 최대 10000개 이므로 20의 10000제곱...이 될 것 같다. 아 그리고 왼쪽 오른쪽 둘 다 돌리는 것은...왠지 필요해 보인다...
그럼 10*10 으로 100가지 경우니까 100의 10000제곱...?
일단 dp로 접근해보면 d[n][left][right] = n번 나사를 왼쪽으로 left번, 오른쪽으로 right번 돌리면서 시작하는 경우에 필요한 최소 회전 칸 수
d[n][left][right]=Min( left:0~9, right:0~9) (d[n+1][left][right]) + left+right
그럼 시간 복잡도가 10000 * 10 * 10 * 100 으로... 1억.. 가능은 해 보인다.
생각만 해서는 문제점을 찾기 힘들다. 구현해 봐야겠다.
구현해 보면서 생각해보니 d[n][num] = n번 나사의 숫자가 num일 때 원하는 상태로 바꾸기 위한 최소 회전 칸 수
이렇게 놓는 것이 나아보인다. 갑자기 확 간단해진 것 같다. 아 그런데, 문제는 n번 나사를 어떻게 돌리냐에 따라 n+1, n+2...이렇게 밑의 나사들도 영향을 받기 때문에 안될 것 같다.
오른쪽으로 돌리는 경우는 상관없지만, 왼쪽으로 돌리는 경우는 아래 나사들에 영향을 준다.
왼쪽으로 돌리면 그 아래 나사들이 같은 칸 만큼 움직인다. 아 그럼 d[n][num][left]로 지금까지 위에서 왼쪽으로 몇 번 움직였는지를 기록하면 될 것 같다. 왼쪽으로 움직이는 것이 누적된 만큼 움직였을 것이고, 또한 왼쪽으로 움직인 것의 누적된 값이 아래에 위치한 숫자 나사들의 상태를 결정하므로 이렇게 하면 될 것 같다.
d[n][num][left]=n번 나사의 숫자가 num이고 ... 가 아니라 n번 나사의 숫자가 무엇인지는 위에서부터 누적된 left만 알면 알 수 있다...
오잉?
그럼 d[n][left]=n번 나사를 돌릴 차례일때 n-1번 나사까지 왼쪽으로 총 left번 돌린 경우에 앞으로 원하는 상태로 바꾸기 위한 최소 회전 칸 수...
d[n][left]
= MIN((leftMove : 0~9, rightMove : 0~9) d[n+1][left+leftMove] ) + leftMove+rightMove
가 되는 것이다
오... 할만하다 역시 생각만 해서는 안된다. 생각만 하지말고 그 생각을 적어봐야 한다. 어느정도 구상이 되면 구현도 해보려고 하고 막히면 다시 생각하되 이렇게 계속 기록하고 적어야 한다. 그래야 생각이 난다.
일단 위의 것을 구현해 봐야겠다. 음 바로 구현하려고 하니까 left가 너무 크다...n이 최대 10000 이기 때문에 누적되면 최대 10만...? 아니 20만도 될 수 있나? 음 고민하다가 문득 떠오른 생각이 아까 풀었던 조세퍼스2 문제의 풀이에서와 좀 비슷한 상황이다. 바로 나사도 조세퍼스 처럼 원형이다! 그렇기 때문에 0~9까지 있는데 왼쪽으로 10번 돌린 것은 0번 돌린 것과 같다. 11번 돌린 것은 1번, 12번은 2번... 그렇다. 바로 누적합%10을 해도 결국은 똑같다.
그러니까 배열의 크기는 d[10000][10]으로 할 수 있다! 오 엄청나다. 아까 조세퍼스2 문제를 복습한답시고 풀지 않았다면 생각 못했을 것 같기도 하다.
일단 구현을 해서 예제에 대한 최소 회전 칸 수는 나온다. 이제 어떤 나사를 어느 방향으로 몇 칸 회전 했는지를 구해야 한다.
음 근데 어느 방향으로 몇 칸 회전했는지를 구하려고 예제도 읽어보고 하는데 아무래도 이 문제에서는 한 쪽으로만 움직여야 하는 것 같다. 나는 구현을 양쪽 방향으로 구현 했는데... 음 그렇다면 좀 수정해야겠다. 이 정도 바꾸는 건 쉬우니.. 그냥 이중 for문을 left, right 따로 계산하도록 for문 2개로 바꿨다.
그리고 어느 방향으로 몇 칸 회전했는지는 최소값이 갱신될 때마다 배열에 넣었다. 이 부분은 쉬웠다. 근데 제출하니까 틀렸다... 고민하던 중 내가 가장 중요한 한 가지를 안넣었다. 바로 이 것은 원형이다. 0에서 9로 넘어가고 9에서 0으로 넘어가는 것을 깜박했다.
음 고쳤는데 고쳐놓고 출력해보니 어느방향으로 몇 칸 회전했는지가 틀리게 나온다. 어느 방향으로 몇 칸 회전했는지를 구할 때 최소값이 갱신될 때마다 배열에 넣는 방식이 틀린 것 같다. 생각해보니 최소인 경우가 여러가지 있을 수 있고 그 경우들이 앞 뒤가 맞게 열결되어야 하기 때문에 그냥 일차원 배열에 넣는 방식으로는 잘못될 것 같다.
결국 그냥 dp를 재귀적으로 구현한 것과 비슷하게 출력하는 것을 구현했고 AC를 받았다.
시간이 12ms로 다른 사람들에 비해 좀 더 걸리는 편이다. 다른 분들의 코드를 보면서 깨달은 것이.. 나처럼 굳이 for문을 써서 모든 경우를 해볼 필요가 없다는 것이다... 왼쪽 몇 칸 오른 쪽 몇 칸이 아니라 그냥 한 번에 왼쪽 또는 오른쪽 둘 중 하나로만 움직여야 하니까 원하는 번호가 되도록 얼마나 움직여야 하는지 계산해서 하면 될 거 같은데...
일단 오른쪽으로 움직이는 것은 최소한으로 움직이는 게 좋다. 그런데 문제는 왼쪽인데, 왼쪽으로 도는 것은.. 아 왼쪽으로 도는 것도 움직이는 것을 최소한으로 하는 게 좋을 것이다. 왜냐하면 어차피 왼쪽으로 최소한으로 움직이든, 한 바퀴 더 돌아서 움직이든 그 아래에 오는 나사들의 위치는 같을 것이기 때문이다. 즉 예를 들어 4에서 5를 만들 때 1칸 움직이는 것이나 11칸 움직이는 것이나 결국 아래 나사들은 똑같이 1칸 움직인 꼴이 된다.
그럼 코드를 좀 수정해 봐야겠다. 수정해서 8ms를 받았다. 4ms도 꽤 많지만, 일단은 이 정도로 해야겠다.
그리고 이 문제는 처음 봤을 때는 어떻게 풀어야 할지 감조차 안 왔는데... 이렇게 내가 생각해서 풀 수 있다는 게 신기하면서도 감격스럽다. 열심히 해야겠다.
일단 최소 몇 칸을 돌려야 하는지에 대해 먼저 생각해보자.
처음에는 위에 것을 우선적으로 최대한 많이 돌려야 하나? 우선적으로 어떤 것을 돌리는 게 최소가 될까..? 라든지 .. 좀 찾아보려 했지만 찾지 못했고, 일단 모든 경우를 다 해본다고 하면 각 숫자 나사마다 왼쪽으로 9칸 오른쪽으로 9칸까지... 안 움직이는 경우까지 포함해서 20가지 경우가 있을 것이다. 그런데 숫자 나사의 개수가 최대 10000개 이므로 20의 10000제곱...이 될 것 같다. 아 그리고 왼쪽 오른쪽 둘 다 돌리는 것은...왠지 필요해 보인다...
그럼 10*10 으로 100가지 경우니까 100의 10000제곱...?
생각만 해서는 문제점을 찾기 힘들다. 구현해 봐야겠다.
구현해 보면서 생각해보니 d[n][num] = n번 나사의 숫자가 num일 때 원하는 상태로 바꾸기 위한 최소 회전 칸 수
이렇게 놓는 것이 나아보인다. 갑자기 확 간단해진 것 같다. 아 그런데, 문제는 n번 나사를 어떻게 돌리냐에 따라 n+1, n+2...이렇게 밑의 나사들도 영향을 받기 때문에 안될 것 같다.
오른쪽으로 돌리는 경우는 상관없지만, 왼쪽으로 돌리는 경우는 아래 나사들에 영향을 준다.
왼쪽으로 돌리면 그 아래 나사들이 같은 칸 만큼 움직인다. 아 그럼 d[n][num][left]로 지금까지 위에서 왼쪽으로 몇 번 움직였는지를 기록하면 될 것 같다. 왼쪽으로 움직이는 것이 누적된 만큼 움직였을 것이고, 또한 왼쪽으로 움직인 것의 누적된 값이 아래에 위치한 숫자 나사들의 상태를 결정하므로 이렇게 하면 될 것 같다.
d[n][num][left]=n번 나사의 숫자가 num이고 ... 가 아니라 n번 나사의 숫자가 무엇인지는 위에서부터 누적된 left만 알면 알 수 있다...
오잉?
그럼 d[n][left]=n번 나사를 돌릴 차례일때 n-1번 나사까지 왼쪽으로 총 left번 돌린 경우에 앞으로 원하는 상태로 바꾸기 위한 최소 회전 칸 수...
d[n][left]
= MIN((leftMove : 0~9, rightMove : 0~9) d[n+1][left+leftMove] ) + leftMove+rightMove
가 되는 것이다
오... 할만하다 역시 생각만 해서는 안된다. 생각만 하지말고 그 생각을 적어봐야 한다. 어느정도 구상이 되면 구현도 해보려고 하고 막히면 다시 생각하되 이렇게 계속 기록하고 적어야 한다. 그래야 생각이 난다.
일단 위의 것을 구현해 봐야겠다. 음 바로 구현하려고 하니까 left가 너무 크다...n이 최대 10000 이기 때문에 누적되면 최대 10만...? 아니 20만도 될 수 있나? 음 고민하다가 문득 떠오른 생각이 아까 풀었던 조세퍼스2 문제의 풀이에서와 좀 비슷한 상황이다. 바로 나사도 조세퍼스 처럼 원형이다! 그렇기 때문에 0~9까지 있는데 왼쪽으로 10번 돌린 것은 0번 돌린 것과 같다. 11번 돌린 것은 1번, 12번은 2번... 그렇다. 바로 누적합%10을 해도 결국은 똑같다.
그러니까 배열의 크기는 d[10000][10]으로 할 수 있다! 오 엄청나다. 아까 조세퍼스2 문제를 복습한답시고 풀지 않았다면 생각 못했을 것 같기도 하다.
일단 구현을 해서 예제에 대한 최소 회전 칸 수는 나온다. 이제 어떤 나사를 어느 방향으로 몇 칸 회전 했는지를 구해야 한다.
음 근데 어느 방향으로 몇 칸 회전했는지를 구하려고 예제도 읽어보고 하는데 아무래도 이 문제에서는 한 쪽으로만 움직여야 하는 것 같다. 나는 구현을 양쪽 방향으로 구현 했는데... 음 그렇다면 좀 수정해야겠다. 이 정도 바꾸는 건 쉬우니.. 그냥 이중 for문을 left, right 따로 계산하도록 for문 2개로 바꿨다.
음 고쳤는데 고쳐놓고 출력해보니 어느방향으로 몇 칸 회전했는지가 틀리게 나온다. 어느 방향으로 몇 칸 회전했는지를 구할 때 최소값이 갱신될 때마다 배열에 넣는 방식이 틀린 것 같다. 생각해보니 최소인 경우가 여러가지 있을 수 있고 그 경우들이 앞 뒤가 맞게 열결되어야 하기 때문에 그냥 일차원 배열에 넣는 방식으로는 잘못될 것 같다.
결국 그냥 dp를 재귀적으로 구현한 것과 비슷하게 출력하는 것을 구현했고 AC를 받았다.
시간이 12ms로 다른 사람들에 비해 좀 더 걸리는 편이다. 다른 분들의 코드를 보면서 깨달은 것이.. 나처럼 굳이 for문을 써서 모든 경우를 해볼 필요가 없다는 것이다... 왼쪽 몇 칸 오른 쪽 몇 칸이 아니라 그냥 한 번에 왼쪽 또는 오른쪽 둘 중 하나로만 움직여야 하니까 원하는 번호가 되도록 얼마나 움직여야 하는지 계산해서 하면 될 거 같은데...
일단 오른쪽으로 움직이는 것은 최소한으로 움직이는 게 좋다. 그런데 문제는 왼쪽인데, 왼쪽으로 도는 것은.. 아 왼쪽으로 도는 것도 움직이는 것을 최소한으로 하는 게 좋을 것이다. 왜냐하면 어차피 왼쪽으로 최소한으로 움직이든, 한 바퀴 더 돌아서 움직이든 그 아래에 오는 나사들의 위치는 같을 것이기 때문이다. 즉 예를 들어 4에서 5를 만들 때 1칸 움직이는 것이나 11칸 움직이는 것이나 결국 아래 나사들은 똑같이 1칸 움직인 꼴이 된다.
그럼 코드를 좀 수정해 봐야겠다. 수정해서 8ms를 받았다. 4ms도 꽤 많지만, 일단은 이 정도로 해야겠다.
그리고 이 문제는 처음 봤을 때는 어떻게 풀어야 할지 감조차 안 왔는데... 이렇게 내가 생각해서 풀 수 있다는 게 신기하면서도 감격스럽다. 열심히 해야겠다.
2016년 10월 4일 화요일
ACM ICPC 인터넷 예선 L번
코드)
#include <cstdio>
#include <vector>
using namespace std;
int truck[1000];
int main() {
int n, len, l;
scanf("%d %d %d", &n, &len, &l);
for(int i=0; i<n; i++) {
scanf("%d", &truck[i]);
}
int time=0, idx=0;
int pWeight=l;
int tPos[1000]={0, };
vector<int> moving;
while(true) {
if(idx<n && truck[idx]<=pWeight) {
pWeight-=truck[idx];
moving.push_back(idx);
idx++;
continue;
}
while(moving.size()) {
bool pass=false;
for(int i=0; i<moving.size(); i++) {
int idx2=moving[i];
tPos[idx2]++;
if(tPos[idx2]>len) {
pWeight+=truck[idx2];
pass=true;
moving.erase(moving.begin()+i);
break;
}
}
time++;
//앞에 다리를 통과하는 동시에 다리로 들어오기 때문에 시간을
//한 번 더 세는 것이 된다. 그래서 time--를 해준다.
if(pass && idx<n && pWeight>=truck[idx]) time--;
if(pass) break;
}
if(idx==n && moving.size()==0) break;
}
printf("%d\n", time);
return 0;
}
#include <cstdio>
#include <vector>
using namespace std;
int truck[1000];
int main() {
int n, len, l;
scanf("%d %d %d", &n, &len, &l);
for(int i=0; i<n; i++) {
scanf("%d", &truck[i]);
}
int time=0, idx=0;
int pWeight=l;
int tPos[1000]={0, };
vector<int> moving;
while(true) {
if(idx<n && truck[idx]<=pWeight) {
pWeight-=truck[idx];
moving.push_back(idx);
idx++;
continue;
}
while(moving.size()) {
bool pass=false;
for(int i=0; i<moving.size(); i++) {
int idx2=moving[i];
tPos[idx2]++;
if(tPos[idx2]>len) {
pWeight+=truck[idx2];
pass=true;
moving.erase(moving.begin()+i);
break;
}
}
time++;
//앞에 다리를 통과하는 동시에 다리로 들어오기 때문에 시간을
//한 번 더 세는 것이 된다. 그래서 time--를 해준다.
if(pass && idx<n && pWeight>=truck[idx]) time--;
if(pass) break;
}
if(idx==n && moving.size()==0) break;
}
printf("%d\n", time);
return 0;
}
ACM ICPC 인터넷 예선 A번
1) root에서 leaf node까지의 최장 경로를 구한다.
2) 그 최장 경로값을 루트에서 리프까지의 거리로 지정하고
3) 상위 노드에 연결된 간선부터 최대한 증가시켜준다.
구현)
1)
code)
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;
void dfs(int, int);
void dfs2(int, int);
vector<vector<pair<int, int> > > adj(2500000);
int maxDist[2500000]={0, };
int ans=0;
int main() {
int k;
scanf("%d", &k);
//root : 1
for(int i=1; i<(1<<k); i++) {
for(int j=0; j<2; j++) {
int cost;
scanf("%d", &cost);
adj[i].push_back(make_pair(2*i+j, cost));
ans+=cost;
}
}
dfs(1, -1);
dfs2(1, -1);
printf("%d\n", ans);
return 0;
}
void dfs2(int node, int p) {
for(int i=0; i<adj[node].size(); i++) {
int child=adj[node][i].first;
if(child==p) continue;
int cost=adj[node][i].second;
dfs2(child, node);
int add=(maxDist[node]-maxDist[child])-cost;
adj[node][i].second+=add;
ans+=add;
}
}
void dfs(int node, int p) {
maxDist[node]=0;
for(int i=0; i<adj[node].size(); i++) {
int child=adj[node][i].first;
if(child==p) continue;
int cost=adj[node][i].second;
dfs(child, node);
maxDist[node]=max(maxDist[node], maxDist[child]+cost);
}
}
2) 그 최장 경로값을 루트에서 리프까지의 거리로 지정하고
3) 상위 노드에 연결된 간선부터 최대한 증가시켜준다.
구현)
1)
code)
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;
void dfs(int, int);
void dfs2(int, int);
vector<vector<pair<int, int> > > adj(2500000);
int maxDist[2500000]={0, };
int ans=0;
int main() {
int k;
scanf("%d", &k);
//root : 1
for(int i=1; i<(1<<k); i++) {
for(int j=0; j<2; j++) {
int cost;
scanf("%d", &cost);
adj[i].push_back(make_pair(2*i+j, cost));
ans+=cost;
}
}
dfs(1, -1);
dfs2(1, -1);
printf("%d\n", ans);
return 0;
}
void dfs2(int node, int p) {
for(int i=0; i<adj[node].size(); i++) {
int child=adj[node][i].first;
if(child==p) continue;
int cost=adj[node][i].second;
dfs2(child, node);
int add=(maxDist[node]-maxDist[child])-cost;
adj[node][i].second+=add;
ans+=add;
}
}
void dfs(int node, int p) {
maxDist[node]=0;
for(int i=0; i<adj[node].size(); i++) {
int child=adj[node][i].first;
if(child==p) continue;
int cost=adj[node][i].second;
dfs(child, node);
maxDist[node]=max(maxDist[node], maxDist[child]+cost);
}
}
BOJ 3108 로고
문제가 복잡해 보이지만 사실 간단하다.
입력으로 주어지는 직사각형을 그래프로 보면, 연결되지 않은 그래프의 개수를 세는 문제로 볼 수 있다. component의 개수를 세는 문제로 볼 수 있다.
예전에 풀 때는 좀 무식하게(?) 입력으로 주어지는 직사각형을 그래프로 나타내고 dfs를 돌려서 직사각형을 구성하는 한 점 한 점을 일일이 탐색하면서 component를 셌는데...
yukariko님(disjoint set을 이용하셨고, 나는 disjoint set을 쓰지는 않지만 직사각형끼리 연결된 것을 판별하는 것은 공통으로 필요)의 방법을 보면 component를 세긴 하지만, 직사각형을 구성하는 한 점 한 점을 일일이 탐색하는 것이 아니라 직사각형을 하나씩 본다. 그렇기 때문에 그 직사각형과 다른 직사각형이 연결되어 있는지를 판단하는 것이 매우 중요한데 문제의 조건에 보면 한 직사각형의 정보는 직사각형의 대각선의 양 끝 점인 (x1, y1), (x2, y2) 이렇게 두 점으로 주어진다.
그리고 x1<x2 and y1<y2 라는 조건이 있다. 이 조건이 성립하려면 항상 (x1, y1) 의 오른쪽 위 대각선 끝에 (x2, y2)가 위치하게 된다.
한 직사각형과 다른 직사각형이 연결되어 있는 경우는 여러가지 경우가 있다. 그래서 이것을 (x1, y2), (x2, y2)를 이용해서 구현하려면 꽤 복잡해질 것 같다. 그럼 어떻게 해야할까? yukariko님의 경우 연결된 경우를 보는 것이 아니라 연결이 되지 않는 경우를 보시는데, 연결이 되지 않는 경우가 그 경우의 수가 적고 간단하다. 그리고 그 외의 경우는 다 연결이 되는 경우이기 때문에 훨씬 간단히 구현할 수 있다.
그리고 구현할 때는 x1<x2 과 y1<y2 라는 조건을 잘 생각해서 (x1, y1), (x2, y2)를 잘 비교하면 되는데, 연결되지 않는 경우를 보면 크게 두 가지로 볼 수 있다. 한 직사각형이 다른 직사각형의 안에 포함이 되거나 혹은 아예 떨어져 있거나 이렇게 두 가지인데,
한 직사각형(A)이 다른 직사각형(B) 안에 들어간 경우는 A의 (x2, y2)가 B의 (x2, y2)보다 모두 작아야 하고, A의 (x1, y2)이 B의 (x1, y1)보다 모두 커야한다.
그리고 A와 B가 아예 떨어져 있을 경우 A가 왼쪽, B가 오른쪽에 위치한다고 하면 A의 (x2, y2)와 B의 (x1, y1)만 비교하면 된다. 왜냐하면 x1<x2, y1<y2라는 조건때문이다.
구현해 봐야겠다. WA를 받아서... 예전의 정답코드랑 비교해 봤는데 완전 거의 똑같아서 도대체 뭐가 문제일까 고민하다가 랜덤으로 데이터를 생성해서 비교해봤다...
아 결국 알아냈다. 이게 처음에는 (0, 0)에서 시작을 하기 때문에 (0, 0)에 직사각형이 있을 경우 펜을 들어 올리지 않고 바로 그려도 되므로 (최종적으로 구한 값-1) 이 정답인데,
나는 (0, 0)이라는 좌표가 들어올 경우에만 -1을 빼주는 식으로 했다. (0, 0)이라는 좌표가 들어오지 않아도 분명 (0, 0)을 지나는 직사각형은 있을 수 있는데... 이 당연한 걸 왜 생각도 못했을까.. 정말 오늘도 내가 틀릴리 없어 -> 아 내가 멍청했구나... 를 깨닫는다.
이것을 쉽게 구현하는 방법은 입력으로 받은 직사각형 외에, (x1, y1), (x2, y2)가 모두 (0, 0)인 직사각형(점)을 추가하고 최종 답에서 -1을 빼주면 된다.
왜냐하면, 입력으로 주어진 직사각형들이 (0, 0)을 지나지 않는다면 추가한 (0, 0)때문에 하나 더 count되므로 당연히 -1을 빼줘야 하고, 입력으로 주어진 직사각형들이 (0, 0)을 지난다면 count가 하나 더 되지는 않지만 -1을 빼줘야 한다.
AC를 받았다.
입력으로 주어지는 직사각형을 그래프로 보면, 연결되지 않은 그래프의 개수를 세는 문제로 볼 수 있다. component의 개수를 세는 문제로 볼 수 있다.
예전에 풀 때는 좀 무식하게(?) 입력으로 주어지는 직사각형을 그래프로 나타내고 dfs를 돌려서 직사각형을 구성하는 한 점 한 점을 일일이 탐색하면서 component를 셌는데...
yukariko님(disjoint set을 이용하셨고, 나는 disjoint set을 쓰지는 않지만 직사각형끼리 연결된 것을 판별하는 것은 공통으로 필요)의 방법을 보면 component를 세긴 하지만, 직사각형을 구성하는 한 점 한 점을 일일이 탐색하는 것이 아니라 직사각형을 하나씩 본다. 그렇기 때문에 그 직사각형과 다른 직사각형이 연결되어 있는지를 판단하는 것이 매우 중요한데 문제의 조건에 보면 한 직사각형의 정보는 직사각형의 대각선의 양 끝 점인 (x1, y1), (x2, y2) 이렇게 두 점으로 주어진다.
그리고 x1<x2 and y1<y2 라는 조건이 있다. 이 조건이 성립하려면 항상 (x1, y1) 의 오른쪽 위 대각선 끝에 (x2, y2)가 위치하게 된다.
한 직사각형과 다른 직사각형이 연결되어 있는 경우는 여러가지 경우가 있다. 그래서 이것을 (x1, y2), (x2, y2)를 이용해서 구현하려면 꽤 복잡해질 것 같다. 그럼 어떻게 해야할까? yukariko님의 경우 연결된 경우를 보는 것이 아니라 연결이 되지 않는 경우를 보시는데, 연결이 되지 않는 경우가 그 경우의 수가 적고 간단하다. 그리고 그 외의 경우는 다 연결이 되는 경우이기 때문에 훨씬 간단히 구현할 수 있다.
그리고 구현할 때는 x1<x2 과 y1<y2 라는 조건을 잘 생각해서 (x1, y1), (x2, y2)를 잘 비교하면 되는데, 연결되지 않는 경우를 보면 크게 두 가지로 볼 수 있다. 한 직사각형이 다른 직사각형의 안에 포함이 되거나 혹은 아예 떨어져 있거나 이렇게 두 가지인데,
한 직사각형(A)이 다른 직사각형(B) 안에 들어간 경우는 A의 (x2, y2)가 B의 (x2, y2)보다 모두 작아야 하고, A의 (x1, y2)이 B의 (x1, y1)보다 모두 커야한다.
그리고 A와 B가 아예 떨어져 있을 경우 A가 왼쪽, B가 오른쪽에 위치한다고 하면 A의 (x2, y2)와 B의 (x1, y1)만 비교하면 된다. 왜냐하면 x1<x2, y1<y2라는 조건때문이다.
구현해 봐야겠다. WA를 받아서... 예전의 정답코드랑 비교해 봤는데 완전 거의 똑같아서 도대체 뭐가 문제일까 고민하다가 랜덤으로 데이터를 생성해서 비교해봤다...
아 결국 알아냈다. 이게 처음에는 (0, 0)에서 시작을 하기 때문에 (0, 0)에 직사각형이 있을 경우 펜을 들어 올리지 않고 바로 그려도 되므로 (최종적으로 구한 값-1) 이 정답인데,
나는 (0, 0)이라는 좌표가 들어올 경우에만 -1을 빼주는 식으로 했다. (0, 0)이라는 좌표가 들어오지 않아도 분명 (0, 0)을 지나는 직사각형은 있을 수 있는데... 이 당연한 걸 왜 생각도 못했을까.. 정말 오늘도 내가 틀릴리 없어 -> 아 내가 멍청했구나... 를 깨닫는다.
이것을 쉽게 구현하는 방법은 입력으로 받은 직사각형 외에, (x1, y1), (x2, y2)가 모두 (0, 0)인 직사각형(점)을 추가하고 최종 답에서 -1을 빼주면 된다.
왜냐하면, 입력으로 주어진 직사각형들이 (0, 0)을 지나지 않는다면 추가한 (0, 0)때문에 하나 더 count되므로 당연히 -1을 빼줘야 하고, 입력으로 주어진 직사각형들이 (0, 0)을 지난다면 count가 하나 더 되지는 않지만 -1을 빼줘야 한다.
AC를 받았다.
2016년 10월 3일 월요일
BOJ 1289 트리의 가중치
트리의 성질 중 하나가 어느 두 정점 간에도 유일하게 하나의 경로가 존재한다는 것인데, 경로의 가중치를 경로에 해당하는 간선들의 가중치 곱으로 정의할 때, 모든 경로의 가중치들의 합인 트리의 가중치를 구하는 문제이다.
N제한이 10만인데, N개의 정점 중 2개의 정점을 선택하는 경우는 N C 2 = N*(N-1)/2 이다.
직접 곱을 다 구해서 합을 구하기에는 N이 너무 크다.
그렇다면 어떻게 해야할까? 구하고자 하는 것이 모든 경로의 가중치들의 합이기 때문에 분명 뭔가 규칙이 있을 것 같다.
일단 규칙을 찾기 위해 작은 트리를 내가 직접 그려 봐야겠다. 음 잘 모르겠다...
일단 빌라봉 문제를 통해 트리에 대해 공부했던 것이 거의 기억이 안난다. 일단 이참에 빌라봉부터 다시 공부해보고 풀어 봐야겠다.
N제한이 10만인데, N개의 정점 중 2개의 정점을 선택하는 경우는 N C 2 = N*(N-1)/2 이다.
직접 곱을 다 구해서 합을 구하기에는 N이 너무 크다.
그렇다면 어떻게 해야할까? 구하고자 하는 것이 모든 경로의 가중치들의 합이기 때문에 분명 뭔가 규칙이 있을 것 같다.
일단 규칙을 찾기 위해 작은 트리를 내가 직접 그려 봐야겠다. 음 잘 모르겠다...
일단 빌라봉 문제를 통해 트리에 대해 공부했던 것이 거의 기억이 안난다. 일단 이참에 빌라봉부터 다시 공부해보고 풀어 봐야겠다.
피드 구독하기:
글 (Atom)