99코딩

정사각형에 2차원 배열인거 보고 분할정복 생각했지만 천천히 다시 읽어보니 관련 없는 문제였다

위에서 우하단을 기준으로 좌상단, 우상단, 좌하단이 1이상이면 정사각형

여기서 우하단에 네 값 중 가장 작은 값 + 1을 하면 해당 정사각형의 한 변의 길이가 됨

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> board)
{
    int answer = board[0][0];
    
    int row = board.size();
    int col = board[0].size();
    
    // (1, 1)부터 시작 > 우하단을 기준으로 하기 때문
    for(int i = 1; i < row; i++) {
        for(int j = 1; j < col; j++) {
        	//0이면 정사각형이 불가능하고 1보다 크면 이미 확인한 구간이지만 중복된 구간을 체크하지 않기 때문에 1보다 클 일이 없음
            if(board[i][j] == 1) {
                board[i][j] = min({board[i-1][j-1], board[i-1][j], board[i][j-1]}) + 1;
                answer = max(answer, board[i][j]);
            }
        }
    }

    return answer * answer;
}

• 서로 같은 거리에서 토크 값이 같으려면 몸무게의 비율 = 1:1
• 2m, 4m 거리에서 토크 값이 같으려면 몸무게의 비율 = 1:2
• 2m, 3m 거리에서 토크 값이 같으려면 몸무게의 비율 = 3:2 = 1:3/2
• 3m, 4m 거리에서 토크 값이 같으려면 몸무게의 비율 = 4:3 = 1:4/3

> 특정 인원의 몸무게를 weight라 할 때 weight값의 1:1, 1:2, 1:3/2, 1:4/3에 해당하는 값이 존재하는지 확인해야함

> weightA와 weightB가 다른 경우에는 단순히 weightB에 해당하는 인원 수를 answer에 더하면 되지만 같은 경우에는 중복을 제거하기 위해 n명 중에서 2명을 뽑는 경우의 수 식을 이용해야함

#include <string>
#include <vector>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    // 각 몸무게에 해당하는 인원 수 저장용 배열
    vector<long long> count(1001, 0);
    long long weight = 0;
    
    // index을 몸무게로 가지는 인원의 수를 저장
    for(int i = 0; i < weights.size(); i++) {
        count[weights[i]]++;
    }
    
    // 특정 몸무게가 2명 이상일 경우 n(n-1)/2 식을 통해 짝의 수를 구함
    for(int i = 100; i < 1001; i++) {
        if(count[i] >= 2) {
            answer += (count[i] * (count[i] - 1)) / 2;
        }
    }
    
    //weight의 1:2, 1:3/2, 1:4/3에 해당하는 몸무게를 가지는 인원 수를 구해서 짝을 만듦
    for(int i = 0; i < weights.size(); i++) {
        // 1:2
        weight = weights[i] * 2;
        if(weight <= 1000) answer += count[weight];
        
        // 2:3
        if(weights[i] % 2 == 0) {
            weight = weights[i] * 3 / 2;
            if(weight <= 1000) answer += count[weight];
        }
        
        // 3:4
        if(weights[i] % 3 == 0) {
            weight = weights[i] * 4 / 3;
            if(weight <= 1000) answer += count[weight];
        }
    }
    
    return answer;
}

• arrayA의 카드들에 적힌 모든 숫자를 나눌 수 있고, arrayB의 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a 
• arrayB의 카드들에 적힌 모든 숫자를 나눌 수 있고, arrayA의 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

• 위 둘 중 하나를 만족하는 가장 큰 양의 정수 a를 구해야 함
• 특정 카드들에 적힌 모든 숫자를 나눌 수 있음 => 최대공약수
• 한 쪽의 최대 공약수를 구해서 다른 한 쪽을 나눌 수 없는지 체크 후 양측에 각각 해당하는 값이 있다면 더 큰 값을 리턴

> arrayA의 최대공약수를 구하고 해당 값이 arrayB를 나눌 수 있는지 체크 후 나눌 수 없다면 answer 값과 비교해서 크다면 저장

> arrayB의 최대공약수를 구하고 해당 값이 arrayA를 나눌 수 있는지 체크 후 나눌 수 없다면 answer 값과 비교해서 크다면 저장

#include <string>
#include <vector>

using namespace std;

// 최대 공약수
int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a%b);
}

// 값 비교
int compare(int a, int b) {
    if(a > b) return a;
    return b;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    int length = arrayA.size();
    
    // arrayA의 최대공약수 구하기
    int gcdValue = arrayA[0];
    
    for(int i = 1 ; i < length; i++) {
        gcdValue = gcd(gcdValue, arrayA[i]);
        if(gcdValue == 1) break;
    }
    
    // 최대공약수가 1이면 패스
    if(gcdValue != 1) {
        int cnt = 0;
        
        // arrayB에 나눌 수 있는 값이 있는지 체크
        for(int i = 0; i < length; i++) {
            if(arrayB[i] % gcdValue == 0) break;    
            cnt++;
        }
        
        //cnt == length면 answer = 최대공약수
        if(cnt == length) answer = gcdValue;
    }
    
    // arrayB의 최대공약수 구하기
    gcdValue = arrayB[0];
    
    for(int i = 0; i < length; i++) {
        gcdValue = gcd(gcdValue, arrayB[i]);
        if(gcdValue == 1) break;
    }
    
    // 최대공약수가 1이면 패스
    if(gcdValue != 1) {
        int cnt = 0;
        
        // arrayA에 나눌 수 있는 값이 있는지 체크
        for(int i = 0; i < length; i++) {
            if(arrayA[i] % gcdValue == 0) break;
            cnt++;
        }
        
        //cnt == length면 answer와 비교해서 더 큰 놈을 answer에 저장
        if(cnt == length) answer = compare(answer, gcdValue);
    }
    
    return answer;
}

• 앞에서부터 n개 단위로 문자열을 잘라 압축시킨 뒤의 문자열 길이가 가장 짧은 n의 값을 구하는 문제

> 1부터 문자열의 길이까지를 단위로 하여 압축한 뒤 개중 가장 짧은 길이를 리턴

> 입력받은 단위만큼 비교하여 압축이 가능한지 가능하다면 총 몇 번 압축 가능한지 판별

> 이후 압축이 가능하다면 압축된 형태로 str을 갱신 후 나머지 구간을 반복

#include <string>
#include <vector>

using namespace std;

// cnt = 압축 단위, str = 문자열
int stringCompressor(int cnt, string str) {
    for(int i = 0; i < str.size();) {
    	// i부터 cnt만큼 문자열을 자름
        string cmpStr = str.substr(i, cnt);
        
        // cmpStr과 같은 문자열의 개수(자신 포함)
        int cntSameStr = 1;
        
        for(int j = i + cnt;j < str.size(); j += cnt) {
        	// j부터 cnt만큼 자른 문자열이 cmpStr과 같으면 cntSameStr++, 다르면 break
            if(cmpStr == str.substr(j, cnt)) cntSameStr++;
            else break;
        }
        
        // cntSameStr == 1이면 같은 문자열 없음으로 다음 구간으로 넘김
        if(cntSameStr == 1) {
            i += cnt;
            continue;
        }
        
        // cntSameStr의 개수 + cmpStr의 형태로 만듦
        cmpStr = to_string(cntSameStr) + cmpStr;
        // 압축되지 않는 나머지 문자열을 자름
        string remainStr = str.substr(i + cnt * cntSameStr);
        // str의 형태를 갱신
        str = str.substr(0, i) + cmpStr + remainStr;
        
        i += cmpStr.size();
    }
    
    return str.size();
}

int solution(string s) {
    int answer = s.size();
    
    //1부터 해당 문자열의 사이즈만큼 압축을 반복
    for(int i = 1; i <= s.size(); i++) {
        answer = min(answer, stringCompressor(i ,s));
    }
    
    return answer;
}

 풀고 나니까 1부터 문자열의 사이즈만큼이 아니라 1부터 문자열 사이즈의 1/2까지만 반복하는 것이 더 효율적이었을 것 같다. 

> 어차피 압축 단위가 문자열의 절반보다 크면 압축 안됨

• 겹치는 구간에 있는 미사일은 하나의 미사일로 전부 요격 가능. 개구간(s, e)의 미사일은 s와 e에서 발사된 요격 미사일로 요격 불가

> 일단 주어지는 targets 배열을 오름차순으로 정렬

> 이후 현재 타겟의 e보다 s가 작은 타겟들을 전부 패스

> 현재 타겟의 e보다 e가 작은 타겟이 나올 시 요격 미사일 수 값을 증가 시키고 e 값을 다음 타겟의 e 값으로 갱신

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> targets) {
    int answer = 0;
    
    // 배열을 오름차순으로 정렬
    sort(targets.begin(), targets.end());
    
    for(int i = 0; i < targets.size();) {
    	// 현재 타겟의 e 값을 저장
        int end = targets[i++][1];
        answer++;
        
        // 다음 타겟의 s가 현재 타겟의 e보다 작다면 반복
        for(; i < targets.size() && targets[i][0] < end;) {
        	//다음 타겟의 e가 현재 타겟의 e보다 작다면 e를 갱신
            if(targets[i][1] < end) end = targets[i][1];
            i++;
        }
    }
    
    return answer;
}

• 잘려나간 종이들은 동일한 패턴을 가짐
• 패턴은 W와 H의 최대공약수만큼 존재
• W를 최대공약수로 나눈 값을 X, H를 최대공약수로 나눈 값을 Y라 할 때 각 패턴에서 사용할 수 없게 되는 정사각형의 개수는 X + Y - 1

> 사용할 수 있는 정사각형의 개수는 (W x Y) - (gcd x (X + Y - 1)) = (W x Y) - (W + Y - gcd)

> 여기서 입력되는 W, H는 1억 이하의 자연수기 때문에 W와 Y를 long 타입으로 캐스팅해주어야함

#include <iostream>

using namespace std;

int gcd(long long a, long long b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

long long solution(int w,int h) {
    return ((long long)w * (long long)h) - (w + h - gcd(w ,h));
}

완전탐색이라 dfs로 접근해보았습니다. 그리고 간선을 하나만 끊어서 2개로 나누는거라 첫 번째 송전탑에서만 dfs를 진행해서 그 값을 송전탑의 개수에서 빼는 것으로 나머지 전력망의 송전탑 수를 구했습니다. 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int graph[101][101] = {0};
int visited[101] = {0};

int dfs(int curTower, int n) {
    if(visited[curTower] == 1) return 0;
    
    int count = 1;
    visited[curTower] = 1;
    
    for(int i = 1; i <= n; i++) {
        if(graph[curTower][i]) {
            count += dfs(i, n);
        }
    }
    
    return count;
}
    
int solution(int n, vector<vector<int>> wires) {
    int answer = 101;
    
    for(int i = 0; i < wires.size(); i++) {
        int x = wires[i][0];
        int y = wires[i][1];
        
        graph[x][y] = 1;
        graph[y][x] = 1;
    }
    
    for(int i = 0; i < wires.size(); i++) {
        int x = wires[i][0];
        int y = wires[i][1];
        graph[x][y] = graph[y][x] = 0;
        
        fill_n(visited, 101, 0);
        int connectedTower1 = 0, connectedTower2;
        
        int count = dfs(1, n);
         
        connectedTower1 = count;
        connectedTower2 = n - count;
        
        answer = min(answer, abs(connectedTower1 - connectedTower2));
        
        graph[x][y] = graph[y][x] = 1;
    }
    
    return answer;
}

각 분마다 몇 개의 객실이 존재해야하는지 구하는 방식으로 접근했다.

1.  room[1450]을 선언하고 0으로 초기화. 청소시간을 고려해서 1440 + 10을 하였다.

2. 각 예약의 대실 시작 시간과 대실 종료 시간 + 청소 시간을 분으로 구함

3. 위의 두 값 사이의 수를 인덱스로 가지는 요소들의 값을 증가

4. room 배열의 최댓값을 리턴

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<string>> book_time) {
    int answer = 0, room[1450] = {0, }; //24*60 + 10 = 1450
    
    for(int i = 0; i < book_time.size(); i++) {
    	//대실 시작 시간을 분으로 전환
        int reserveStart = stoi(book_time[i][0].substr(0, 2)) * 60 + stoi(book_time[i][0].substr(3, 2));
        //대실 종료 시간 + 청소 시간을 분으로 전환
        int reserveEnd = stoi(book_time[i][1].substr(0, 2)) * 60 + stoi(book_time[i][1].substr(3, 2)) + 10;
        
    	//대실 시작 시간부터 종료 시간까지 room배열의 값을 증가
        for(int time = reserveStart; time < reserveEnd; time++) {
            room[time]++;
        }
    }
    
    //room 배열 안의 가장 큰 값이 필요한 최소 객실 수
    for(int num : room)
        if(num > answer) answer = num;
    
    return answer;
}