[BOJ] 수학 1(2)

[BOJ 2869]

 

아... 설명하기 굉장히 어렵군요... 일단 하루가 지날 때마다 총 올라간 거리를 등반과 미끄러짐을 고려하여 구해줍니다. 마지막 날에 정상에 도착하면 끝이므로 미끄러지는 거리는 공짜로 먹고 들어간다고 볼 수 있습니다. 그래서 고려사항에서 빼줍니다. 이제 이 거리 이상 올라갈 때까지 걸리는 시간을 계산해주면 됩니다. 

#include <stdio.h>

int climbdays(int climb, int fall, int distance){
    int climbperday = climb - fall;
    int d = distance - fall;
    return (d / climbperday) + (d % climbperday != 0 ? 1 : 0);
}

int main(){
    int A, B, V;
    scanf("%d%d%d",&A,&B,&V);
    printf("%d",climbdays(A, B, V));
}

 

[BOJ 10250]

 

아... 이제 문제가 점점 길어지고 있습니다. 사실 별거 없습니다. 각 층의 1호, 2호, ..., 순으로 꽉꽉 채워주면 됩니다. 쉽게 할 수 있을 거예요.

#include <stdio.h>

int allocroom(int H, int W, int N){
    int roominfloor = (N + H - 1) / H;
    int roomfloor = N - H * (roominfloor - 1);
    return roomfloor * 100 + roominfloor;
}

int main(){
    int T;
    scanf("%d",&T);
    int H, W, N;
    for(int k=0;k<T;++k){
        scanf("%d%d%d",&H,&W,&N);
        printf("%d\n",allocroom(H,W,N));
    }
}

 

[BOJ 2775]

 

원래는 각 호의 인원을 모두 채운 걸 한 번에 계산하고 한 번에 출력하는 게 중복 없이 가장 효율적이겠지만, 그다지 조건이 힘들지 않아서 하나씩 하는 걸로 했습니다. 그냥 배열 하나에 계속 왼쪽에서 오른쪽으로 더해주면서 구하면 됩니다.

#include <stdio.h>
#include <vector>

using namespace std;

int totalresident(int k, int n){
    vector<int> residents(n+1);
    for(int i=1;i<=n;++i) residents[i] = i;
    for(int j=1;j<=k;++j)
        for(int i=2;i<=n;++i)
            residents[i] += residents[i-1];
    return residents[n];
}

int main(){
    int T;
    scanf("%d",&T);
    int k, n;
    for(int i=0;i<T;++i){
        scanf("%d%d",&k,&n);
        printf("%d\n",totalresident(k,n));
    }
}

 

[BOJ 1011]

 

이 문제는 int의 한계 때문에 삽질을 약간 했습니다. 답 자체는 별거 없습니다. 

 

1번 이동할 때 최대 거리는 1

2번 이동할 때 최대 거리는 1+1

3번 이동할 때 최대 거리는 1+2+1

4번 이동할 때 최대 거리는 1+2+2+1

5번 이동할 때 최대 거리는 1+2+3+2+1

 

2n번 이동할 때 최대 거리는 1+2+...+n+n+...+2+1 = n(n+1)

2n-1번 이동할 때 최대 거리는 1+2+...+n+...+2+1 = n*n

 

그래서 저는 2n번 이동할 때를 기준으로 n의 값을 구해준 후에 그걸로 하나를 빼줄지 말지 결정하는 방식으로 풀었습니다. 만약에 주어진 거리가 n*n과 n(n+1) 사이에 있다면 어떻게 될까요? 꼭대기에서부터 하나씩 빼주면 그 거리는 정확하게 맞출 수 있습니다. 1+2+...+n+n+(n-1)+...+2+1 -> 1+2+...+n+(n-1)+(n-1)+...+2+1 -> 1+2+...+n+(n-1)+(n-2)+...+2+1와 같이 꼭대기에서부터 하나씩 빼주면서 내려가면 n*n까지 갈 수 있습니다. 

 

여기서 삽질한 부분은 stepcount 함수의 distance와 n*n을 비교하는 과정에서 오버플로우가 일어날 수 있었던 것이었고 unsigned로 바꾸어서 해결했습니다.

#include <stdio.h>
#include <math.h>

unsigned int stepcount(unsigned int distance){
    // solve equation n(n+1) = distance
    unsigned int n = ceil(sqrt(distance + 1./4.) - 1./2.);
    if(distance <= n*n) return 2 * n - 1;
    else return 2 * n;
}

int main(){
    int T;
    scanf("%d",&T);
    for(int k=0;k<T;++k){
        int x, y;
        scanf("%d%d",&x,&y);
        printf("%d\n",stepcount(y - x));
    }
}

 

수고하셨습니다.