TIL (22.04.17) 3주차 알고랩 풀이

이 글은 과제 제출 기한이 지났고 사이트 내에서 코드도 열람이 가능해졌기 때문에

풀이를 정리해도 될 것 같아 비공개 글에서 공개글로 전환하였습니다.

<안내>
필자도 배우는 입장이라 틀린점, 잘못된 점이 있을 수 있습니다.
그러니 지적, 피드백 환영합니다.

주가분석

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    while(T--) {
        int t, tmp_old, tmp_mid, tmp_new, input, cnt;
        cnt = 0;
        cin >> t;
        cin >> input;
        tmp_old = tmp_mid = tmp_new = input;
        t--;
        // tmp_old = tmp_mid = tmp_new = 0;

        while(t--){
            // cout << tmp_old << " " << tmp_mid << " " << tmp_new << "\n";
            cin >> input;
            if (input == tmp_new){
                // cout << "while 실행" << "\n";
                continue; // 같은 값을 넣으면 다음 input으로 넘어감
            }
            if (tmp_mid == tmp_new){
                tmp_mid = tmp_new;
                tmp_new = input;
            }
            else {
                tmp_old = tmp_mid;
                tmp_mid = tmp_new;
                tmp_new = input;
            }

            if ((tmp_old < tmp_mid) && (tmp_new < tmp_mid)){
                cnt++;
            // cout << tmp_old << " " << tmp_mid << " " << tmp_new << "\n";                
            // cout << "cnt : " << cnt << "\n";
            }

        } 
        cout << cnt << "\n";

    }
}

개인적으로 제일 까다로웠던 문제. 중간값이 제일 클 때 cnt를 늘리는데, 이 조건을 잘 잡아야함.

 

나같은 경우는, tmp_old와 tmp_mid, tmp_new 변수를 만들어서 조건을 잡았다.

 

들어오는 입력은 input으로 받아서 tmp_new랑 같으면 넘기고, 다를 경우 비교해서 체크

 

첫 조건을 잘 못 잡아서 if (input == tmp_mid)로 잡았는데, 이렇게 잡으면 중간 값이랑 같은 값이 들어오면 넘기게 되는 식이라, 잘못 로직을 잡은 것같다.

사각형 3

#include <iostream>
using namespace std;

char arr[100][100];

int main() {
    int T, n;

    cin >> T;

    while(T--){
        cin >> n;
        for (int j = 1; j < n+1; j++){ // 전체 배열을 .으로 초기화
            for (int i = 1; i < n+1; i++ ){
                arr[i][j] = '.';
                if (i == 1 || i == (n+1)/2 || i == n)
                    arr[i][j] = '|';
                if (j == 1 || j == (n+1)/2 || j == n)
                    arr[i][j] = '-';
                if (i == j)
                    arr[i][j] = '\\';
                if (i == n-j+1)
                    arr[i][j] = '/';
                if ((i == 1 || i == (n+1)/2 || i == n) && (j == 1 || j == (n+1)/2 || j == n))
                    arr[i][j] = '+';
                if (i == (n+1)/2 && j == (n+1)/2)
                    arr[i][j] = '*';
            }
        }

        for (int j = 1; j < n+1; j++){ // 전체 배열을 .으로 초기화
            for (int i = 1; i < n+1; i++){
                cout << arr[i][j];
                if (i == n)
                    cout << "\n";
            }
        }
    }
}

에타에서도 사각형을 욕하는 글이 많아서 이상의 욕은 하지 않겠지만, 정말 사각형으로 출제자들이 많은 생각을 할 수있구나. 라는 생각이 드는 문제.

 

나의 경우엔 if조건문으로 제일 겉에서부터 칠했음 유화 그리듯이 제일 배경 그리고 그 위에 집 그리고 그위에 문그리고 그위에 문고리 그리는(?)

 

이 문제에서 말하면 전체 배열에 "."을 씌우고, 그 위에 각 arr[i][j]의 조건을 따져서 -를 쭉깔고, |를 쭉깔고, /를 쭉깔고 \를 쭉 깐다 그러면 필연적으로 겹치는 공간이 있을텐데 상관 없다. 유화 그리듯이 이미 지정된 공간위에 덧씌우는것이라고 생각하면 됨.

 

마지막에 + 깔고 * 까지 깔면 완벽!
물론 실행시간은 오래 나왔겠지만.. 실행시간 줄이려면 겹치지 않는 공간에서의 처리를 좀 더 생각하면 되긴 했을 것 같음.

 

# 수정 1

13L 에서 for (int j = 1; j <= n; j++) { 

로 부등호를 바꾸면 1~n까지 폐구간임을 좀 더 빠르게 캐치 가능! 

두 사각형의 면적 둘레 구하기

#include <iostream>
using namespace std;

int main() {
    int T, apx, apy, aqx, aqy, bpx, bpy, bqx, bqy, tmpx, tmpy;
    int area, round;
    cin >> T;

    while (T--) {


        cin >> apx >> apy >> aqx >> aqy >> bpx >> bpy >> bqx >> bqy; // a사각형 p좌표 xy, q좌표 xy, b사각형 p좌표 xy, q좌표 xy
        // cout << apx << apy << aqx << aqy << bpx << bpy << bqx << bqy << endl;
        // cout << "minaqx"<< min(aqx,bqx) <<"maxqpx" << max(apx,bpx) << endl;

        tmpx = max((min(aqx,bqx) - max(apx,bpx)),0);
        // cout << tmpx << endl;
        tmpy = max((min(aqy,bqy) - max(apy,bpy)),0);
        // cout << tmpy << endl;
        if (tmpx ==0 || tmpy == 0){
            tmpx = 0;
            tmpy = 0;
            }  // 여기 중괄호 안 넣어서 틀림


        area = (aqx - apx) * (aqy - apy) + (bqx - bpx) * (bqy - bpy) - tmpx * tmpy;
        // cout << area << tmpx << tmpy << endl;
        round =  2*((aqx - apx) + (aqy - apy) + (bqx - bpx) + (bqy - bpy)) - 2 * tmpx - 2 * tmpy;
        cout << area << " " << round << "\n";
        tmpx = 0;
        tmpy = 0;
    }
}

겹치든, 안 겹치든 모든 케이스에서 전체 면적은'두 사각형의 면적 합 - 겹치는 부분의 면적' 으로 같다.

둘레도 마찬가지. 겹치든 안겹치든 모든 케이스에서 둘레의 합은 '두 사각형의 둘레의 합 - 겹치는 부분의 둘레'로 같다.

 

또한 겹치는 조건은 x와 y방향으로 같이 만나야 가능하다. 하나라도 0이 된다면, 둘 다 0으로 만들어버려서 전체 둘레와 넓이에 영향을 주지 못하도록 만들자 .

 

꽤 무난하게 풀었지만, if 실행문에서 중괄호 넣는것을 까먹어서 한참을 헤맸다. 실행문이 두 줄 이상이면 중괄호를 넣지 않으면 첫번쨰 실행문만 실행한다는 것을 잊지말자.

 

# 수정1. 

round 는 C++ 내장함수라서 변수명으로 쓸 때 주의해야함, round라는 변수가 선언되지 않은 다른 함수에서 호출하면 내장함수로 인식할거니까 헷갈릴 수 있음 

 

## 수정2.

30 L,31L 에서 tmpx, tmpy 를 굳이 0으로 초기화 할 필요 없음 왜냐? 16,18L에서 수식으로 초기화하고있으므로! 

두 구간이 차지하는 길이 구하기

#include <iostream>
using namespace std;

int main(){
    int T, ax, ay, bx, by;
    cin >> T;
    while(T--){
        cin >> ax >> ay >> bx >> by;

        if (bx > ay | ax > by){ // 서로 겹치지 않는 경우
            cout << 0 << " " << ay - ax + by - bx << "\n";
        } // 하나가 하나에 포함되는경우
        else if ((bx < ax && ay < by)|(ax < bx && by < ay)){
            cout << min(ay-ax,by-bx) << " " << by - bx + ay - ax - min(ay-ax,by-bx) << "\n";
        }
        else { // 포함되지 않고 겹치는 경우
            cout << min(ay-bx,by-ax) << " " << by - bx + ay - ax - min(ay-bx,by-ax) << "\n";
        }
    }

}

쉽게 푼 문제 a구간의 앞부분을 ax, 뒷부분을 ay, b구간의 앞부분을 bx, 뒷부분을 by라고 입력을 받자 .

 

겹치는 부분에 따라, 빼야하는 부분이 달라진다. 그러고보니 하나가 하나에 포함되는 경우는 max(ay - ax, by - bx) 로도 가능했겠네 음.. 그렇네요

 

# 수정1

10L , 13L에서 | (비트 연산자 or )을 사용했는데, 이 경우는 문제는 없었지만, 다른 수에서 문제가 생길 수 있음 (-1 | 0 하면 이상한 일들이 일어날 수 있음) 그래서 논리로 다가가야할 때는 || 으로 정확하게 풀자. 

 

이번 주 문제는 꽤 쉽게 풀었던 것 같다. 저번주 달팽이문제가 진짜 어려웠음..!