99코딩

• 집합 내의 숫자들 간의 격차가 적을수록 곱이 최대가 됨
• s를 n으로 나눈 몫이 자연수가 아니면(= s가 n보다 작으면) 합이 s인 집합을 만들 수 없으므로 -1 리턴
• 자연수면 나눈 몫을 n개 저장하고 나머지만큼 각 원소에 1씩 더해줌
• 오름차순 정렬 수행

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

using namespace std;

// 집합 내의 숫자들 간의 격차가 적을수록 곱이 최대가 됨
// s를 n으로 나눈 몫이 자연수가 아니면(= s가 n보다 작으면) 합이 s인 집합을 만들 수 없으므로 -1 리턴
// 자연수면 나눈 몫을 n개 저장하고 나머지만큼 각 원소에 1씩 더해줌
// 오름차순 정렬 수행

vector<int> solution(int n, int s) {
    vector<int> answer;
    
    if(n > s) return {-1};
    
    int a = s / n;
    int b = s % n;
    
    for(int i = 0; i < n; i++)
        answer.push_back(a);
    
    for(int i = 0; i < b; i++)
        answer[i]++;
    
    sort(answer.begin(), answer.end());
    
    return answer;
}

• 오른쪽과 아래쪽으로만 이동 가능
• 각 격자마다 해당 격자까지 도달할 수 있는 경로의 수를 저장
• [i][j]에 도달할 수 있는 경로의 수를 점화식으로 나타내면 dp[i][j] = dp[i-1][j] + dp[i][j-1]
• 물에 잠긴 곳은 -1로 저장한 뒤 방문 시 0으로 바꿈

위 조건을 그림으로 나타내면 아래처럼 됨

#include <string>
#include <vector>

using namespace std;

// dp 문제
// 각 격자마다 해당 격자까지 도달할 수 있는 경로 개수를 저장
// 오른쪽과 아래쪽으로만 이동 가능
// 위 조건에 따라 dp[i][j]에 도달할 수 있는 경로의 수는 dp[i-1][j] + dp[i][j-1]
// 물에 잠긴 곳은 -1으로

int dp[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    dp[1][1] = 1;
    
    for(int i = 0; i < puddles.size(); i++)
        dp[puddles[i][1]][puddles[i][0]] = -1;
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            // 시작점일 때
            if((i == 1 && j == 1)) continue;
            
            // 물에 잠긴 곳일 때
            if(dp[i][j] == -1) {
                dp[i][j] = 0;
                continue;
            }
            
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
        }
    }
    
    return dp[n][m];
}

• 야근지수가 최소가 되려면 작업량을 줄이면서 해당 작업량들간의 차이가 최소가 되어야함
• 작업량을 내림차순으로 정렬한 뒤에 높은 값을 -1씩 해주는걸 반복
• > 우선순위 큐에 작업량을 삽입하고 top을 꺼내서 -1 해주고 다시 삽입을 반복

#include <string>
#include <vector>
#include <queue>

using namespace std;

// works의 시간을 줄이면서 works의 작업량들의 값이 비슷해야함
// 예를 들어 [4,3,3]에서 n = 4일 때 [0,3,3]이 되면 작업 하나는 마쳤지만 야근 지수는 제곱을 해서 0 + 9 + 9 = 18이 됨
// 하지만 [2,2,2]가 되면 4 + 4 + 4 = 12로 최소가 됨
// 우선순위 큐로 제일 많이 남은 작업량을 꺼내서 -1 해주고 다시 담는 걸 n번 반복

long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue<int> pq;
    
    for(int i = 0; i < works.size(); i++)
        pq.push(works[i]);
    
    for(int i = 0; i < n; i++) {
        if(pq.empty()) break;
        
        int num = pq.top() - 1;
        pq.pop();
        
        if(num == 0) continue;
        else pq.push(num);
    }
    
    if(pq.empty())
        return 0;
    
    for(int i = 0; !pq.empty(); i++) {
        int num = pq.top();
        answer += num * num ;
        pq.pop();
    }
    
    return answer;
}

• 3레벨에서 의외로 기초적인 dfs/bfs 문제
• 그래도 변수명을 제대로 썼는지 확인하자, 다음 노드로 갱신해야하는데 현재 노드로 갱신하고 있는걸 코드 실행 해보고 알았다...

#include <string>
#include <vector>
#include <queue>

using namespace std;

bool isVisited[200] = {false};
int answer = 0;
queue<int> q;

void bfs(int startNode, int n, vector<vector<int>> computers) {
    q.push(startNode);
    isVisited[startNode] = true;
    
    while(!q.empty()) {
        int curNode = q.front();
        q.pop();
        isVisited[nextNode] = true;
        
        for(int nextNode = 0; nextNode < n; nextNode++) {
            if(computers[curNode][nextNode] == 1 && !isVisited[nextNode]) {
                q.push(nextNode);
                
            }
        }
    }
    
    answer++;
}

int solution(int n, vector<vector<int>> computers) {    
    for(int i = 0; i < n; i++) {
        if(!isVisited[i]) {
            bfs(i, n, computers);
        }
    }
    
    return answer;
}

• 각각 내림차순, 오름차순으로 값을 저장하는 우선순위 큐 2개를 활용
• 삽입은 두 큐에 동시에 수행하고 최댓값 삭제는 내림차순 큐에서 최솟값 삭제는 오름차순 큐에서 수행
• 추가로 삽입을 수행한 횟수와 삭제를 수행한 횟수가 같아지면 두 큐를 모두 비워줘야함 

#include <string>
#include <vector>
#include <sstream>
#include <queue>

using namespace std;

// 우선순위큐 2개를 생성해서 하나는 내림차순, 하나는 오름차순으로 정렬
// 삽입 같은 경우에는 두 큐에 모두 수행
// 최댓값은 내림차순, 최솟값은 오름차순 큐에서 수행
// 이후 하나가 비어있으면 나머지 하나도 비어있는 것이므로 [0, 0] 리턴
// 아니라면 각각 front() 값을 리턴하면 됨

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    priority_queue<int> lesser_pq;
    priority_queue<int, vector<int>, greater<int>> greater_pq;
    int cnt = 0;
    
    for(int i = 0; i < operations.size(); i++) {
        if(operations[i] == "D 1") {
            if(!lesser_pq.empty()) {
                lesser_pq.pop();
                cnt--;
            }
        }
        else if(operations[i] == "D -1") {
            if(!greater_pq.empty()) {
                greater_pq.pop();
                cnt--;
            }
        }
        else {
            string str = "";
            istringstream iss(operations[i]);
            
            iss >> str >> str;
            
            lesser_pq.push(stoi(str));
            greater_pq.push(stoi(str));
            
            cnt++;
        }
        
        if(cnt == 0) {
            while(!lesser_pq.empty()) lesser_pq.pop();
            while(!greater_pq.empty()) greater_pq.pop();
        }
    }
    
    if(lesser_pq.empty()) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else {
        answer.push_back(lesser_pq.top());
        answer.push_back(greater_pq.top());
    }
    
    return answer;
}

• 마지막 열에 거쳐간 숫자의 합의 최댓값들이 있어야함
• 2차원 배열을 만들어서 아래 열로 갈때마다 이 전 2개 칸 중 더 큰 값과 현재 칸의 값을 더한 값을 저장해나가면 됨
• 배열 [i][j]에는 [i-1][j-1], [i-1][j] 중 더 큰 값에 삼각형 [i][j]를 더한 값이 저장됨
• 점화식으로 나타내면 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
• 추가로 왼쪽과 오른쪽 끝에서는 아랫열에 칸이 하나 밖에 없으므로 이에 대한 처리를 해줘야함
• 수행이 끝난 뒤 마지막 열에서 최댓값을 찾아 리턴

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

using namespace std;

// DP 문제
// i 칸에서 i + 1 칸으로 이동할때 i 칸에서에서 j 번째 숫자는 i + 1 칸의 j 또는 j + 1번째 숫자로 이동 가능
// 거쳐간 숫자의 최댓값을 구하려면 [i][j]까지의 합들이 항상 최댓값이 되어야함
// 즉 [i][j]는 [i-1][j-1]과 [i-1][j] 중 큰 값에 원래 [i][j]에 위치한 값을 더한 값이 됨
// 점화식으로 나타내면 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];

// 이게 음수 인덱스가 되면 0으로 인식하게 되어있는건진 잘 모르겠는데 위에 점화식만 반복으로 돌렸는데 문제가 발생하지 않았다
// 그래도 음수 인덱스가 정상은 아니므로 왼쪽 끝과 오른쪽 끝에 대한 처리를 해주자
int dp[500][500];

int solution(vector<vector<int>> triangle) {
    int answer = -1;
    int height = triangle.size();
    dp[0][0] = triangle[0][0];
    
    for(int i = 1; i < height; i++) {
        for(int j = 0; j <= i; j++) {
            // 왼쪽 끝일 때
            if (!j) {
                dp[i][j] = dp[i-1][j] + triangle[i][j];
            }
            // 오른쪽 끝일 때
            else if (i == j) {
                dp[i][j] = dp[i-1][j-1] + triangle[i][j];
            }
            // 해당 없음
            else {
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }
    }
    
    for(int i = 0; i < triangle[height - 1].size(); i++) {
        answer = max(answer, dp[height - 1][i]);
    }
    
    return answer;
}

​

[2. Perforce실행]

 

 

P4V를 실행 시키면 위와 같은 창이 뜬다.

여기서 New를 눌러 사용자를 만들고 워크스페이스를 생성해주면 된다.

 

 

이후 해당 경로에 프로젝트를 넣어주었다.

​

​

[4. 언리얼 에디터와 연결]

 

에디터 우하단의 리비전 컨트롤을 클릭하면

 

 

이미 연결을 해놔서 조금 다르긴한데 위와 같은 창이 뜬다.

여기서 Perforce를 선택하고 서버,사용자명,워크스페이스를 입력 및 선택하면 된다.

​

[5. 외부에서 P4V 서버 접근]

 

 

외부 이용자는 해당 창에서 Server에 서버가 설치된 PC의 IP:1666을 입력하면 된다.

IP는 cmd 창에서 ipconfig 입력으로 알 수 있고

만약 공유기 사용 중이라면 IPTIME 기본 설정 페이지에서 관리도구 > 기본 설정 > 시스템 요약 정보에서 외부 IP 주소를 찾아 입력하면 된다. (포트 포워딩이 되어 있어야함)

 

추가로 방화벽 설정도 해주어야하는데

 

 

Windows Defender 방화벽을 통해 앱 또는 기능 허용을 클릭 후

 

 

위 창에서 설정 변경 클릭 후 다른 앱 허용에서

 

 

Perforce 설치 경로의 Server 폴더에서 p4d.exe와 p4s.exe를 추가해주어야한다.

​

​

• i점에서 라이언이 어피치보다 1발 더 맞춰야 라이언이 득점
• 2발 더 맞춰도 얻는 점수는 같기에 어피치보다 2발 이상 맞추는건 낭비
• 가장 큰 점수 차로 이기는게 여러가지면, 가장 낮은 점수를 더 많이 맞춘 경우를 리턴 > 각 점수마다 위를 반복한 후 남은 화살을 전부 0점에서 소모
• 위를 조건으로 화살 명중 조합을 만들고 각 조합마다 점수를 계산해서 점수차가 가장 큰 경우와 해당 경우가 2개 이상일 시 0점에서 소모된 화살이 더 많은 경우를 리턴
• 점수가 어피치보다 낮으면 -1 리턴

#include <string>
#include <vector>

using namespace std;

// 완전탐색 필요 > dfs 사용

int bestDiff = -1, RyanScore = 0, ApeachScore = 0;
vector<int> score, ryan, apeach, ryanBest;

void checkCondition() {
    int diff = RyanScore - ApeachScore;
    
    // ryan의 점수에서 apeach의 점수를 뺀 값이 0이하면 ryan이 이긴 것이 아님
    if(diff <= 0) return;
    // ryan이 이겼다면
    else {
        // 현재 최고점하고 diff가 같다면
        if(bestDiff == diff) {
            // 가장 낮은 점수를 더 많이 맞힌 경우 구하기
            // 가장 낮은 점수를 맞춘 수가 동일하다면 그 다음으로 낮은 점수로 넘어가야함
            for(int i = 10; i >= 0; i--) {
                // ryan이 0이 아니고 ryanBest가 0인 경우
                if(ryan[i] != 0 && ryanBest[i] == 0) {
                    ryanBest = ryan;
                    break;
                }
                // ryan이 0이고 ryanBest는 0이 아닌 경우
                else if(ryan[i] == 0 && ryanBest[i] != 0)
                    break;
                // 둘의 값이 0이 아니면 비교 필요
                else if(ryan[i] != 0 && ryanBest[i] != 0) {
                    // 둘의 값이 다르면
                    if(ryan[i] != ryanBest[i]) {
                        // ryan이 ryanResult보다 크면
                        if(ryan[i] > ryanBest[i]) {
                            // 점수차는 같으나 배열 갱신 필요
                            ryanBest = ryan;
                            break;
                        }
                    }
                }
            }
        }
        // 현재 최고점보다 ryanScore가 크거나 갱신된 적이 없다면
        else if(diff > bestDiff || bestDiff == -1) {
            // 갱신
            bestDiff = diff;
            ryanBest = ryan;
        }
    }
}

// 점수 계산
void calcScore() {
    int ryanScore = 0;
    int apeachScore = 0;
    
    for(int i = 0; i < 11; i++) {
        // i 배점에서 ryan과 apeach가 맞힌 개수가 동일하면
        if(ryan[i] == apeach[i]) {
            // ryan과 apeach 둘 다 i 점을 맞추지 않았을 때
            if(ryan[i] == 0 && apeach[i] == 0)
                continue;
            else
                apeachScore += 10 - i;
        }
        // 맞힌 개수가 동일하지 않을 때
        else {
            // 라이언이 어피치보다 많이 맞췄으면 라이언 점수 증가 
            if(ryan[i] > apeach[i])
                ryanScore += 10 - i;
            // 아니면 어피치 점수 증가
            else
                apeachScore += 10 - i;
        }
    }
    
    // 라이언 점수
    RyanScore = ryanScore;
    
    // 어피치 점수
    ApeachScore = apeachScore;
}

void dfs(int cnt, int i, int n) {
    // 화살을 전부 사용했으면
    if(cnt == n) {
        // 계산
        calcScore();
        
        // 조건 체크
        checkCondition();
        return;
    }
    
    int remain = n - cnt;
    
    // 가장 큰 점수 차이로 우승하는 방법이 여러가지면, 가장 낮은 점수를 더 많이 맞춰야함
    // 2번째 조건을 위해 i == 10에서 남은 화살이 있으면 전부 소모해야함
    if(i == 10) {
        ryan[i] = remain;
        dfs(cnt + remain, i + 1, n);
        ryan[i] = 0;
    }
    // i == 10이 아닐 때
    else {
        // 남은 화살 수가 apeach[i]보다 크거나 같으면
        if(apeach[i] + 1 <= remain) {
            // apeach[i] + 1을 ryan[i]에 삽입
            ryan[i] = apeach[i] + 1;
            dfs(cnt + ryan[i], i + 1, n);
            ryan[i] = 0;
        }
        
        dfs(cnt, i + 1, n);
    }
}

vector<int> solution(int n, vector<int> info) {
    score.resize(2, 0);
    ryan.resize(11, 0);
    
    apeach = info;
    
    dfs(0, 0, n);
    
    // bestDiff가 갱신된적 없다면 이기는 경우가 없음 > -1 리턴
    if(bestDiff == -1) ryanBest.push_back(-1);
    
    return ryanBest;
}