6주차 모범 답안

[dhdbstjr98]

개요

• 평균 점수 : 6.545점 (미참여자 제외)
• 만점자 : 3명

모범 답안

1. 지우개

문제 보기

정답 : 10명

황지원

import math

n = int(input())


# 1                                 -> 1
# 1 2                               -> 2
# 1 2 3                             -> 2
# 1 2 3 4         -> 2 4            -> 4
# 1 2 3 4 5       -> 2 4            -> 4
# 1 2 3 4 5 6     -> 2 4 6          -> 4
# 1 2 3 4 5 6 7   -> 2 4 6          -> 4
# 1 2 3 4 5 6 7 8 -> 2 4 6 8 -> 4 8 -> 8
# ...
# 1 2 3 ... n     -> ...            -> 2 ^ floor(log_2(n))
print(2 ** int(math.log2(n)))

2. 대칭 차집합

문제 보기

정답 : 10명

전현준

a, b = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

count, i = 0, 0
for an in A:
    while i < b and B[i] <= an:
        if B[i] == an:
            count += 1
        i += 1
        
print(a + b - 2*count)

3. 내리막길

문제 보기

정답 : 7명

손지언

dfs + dp를 이용한 풀이

#include <iostream>
#include <set>

using namespace std;

int slope[502][502];
int cases[502][502];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
int M, N;

bool is_available(int x, int y, int i) {
	bool res = false;

	if (x + dir[i][0] > 0 && x + dir[i][0] <= M && y + dir[i][1] > 0 && y + dir[i][1] <= N) {		
		res = true;
	}

	return res;
}
int getload(int x, int y) {
	int res = 0;
	bool found = false;
	//cout << "x: " << x << ", y: " << y << "\n";
	if (cases[x][y] != -1) {
		//cout << cases[x][y] << "\n";
		return cases[x][y];
	}

	if (x == M && y == N) {
		return 1;
	}

	for (int i = 0; i < 4; i++) {
		if (is_available(x, y, i)) {
			if (slope[x][y] > slope[x + dir[i][0]][y + dir[i][1]]) {
				res += getload (x + dir[i][0], y + dir[i][1]);
			}
			
		}
	}

	//cout << res << "\n";
	cases[x][y] = res;
	return res;
}
int main() {
	cin >> M >> N;
	for (int i = 1; i <= M;i++) {
		for (int j = 1; j <= N; j++) {
			cin >> slope[i][j];
			cases[i][j] = -1;
		}
	}

	cout << getload(1, 1);
}

4. 모두 0으로 만들기

문제 보기

정답 : 3명

손현수

bfs를 이용한 풀이

#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define pii pair<int, int>
#define abs(a) (a>0?a:-a)

int n, weights[200000], a, b, res;
bool visited[200000]={1};
vector<vector<int>> tree(200000, vector<int>());
queue<int> bfsQueue;
stack<pii> calcEdges;
int main()
{
    scanf("%d",&n);
    for(int cnt=0; cnt<n; ++cnt)
        scanf("%d",&weights[cnt]);
     
    for(int cnt=1; cnt<n; ++cnt){
        scanf("%d%d",&a,&b);
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    
    bfsQueue.push(0);
    while(!bfsQueue.empty()){
        int node = bfsQueue.front(); bfsQueue.pop();
        for(int cnt=0; cnt<tree[node].size(); ++cnt){
            int nextNode = tree[node][cnt];
            if(!visited[nextNode]){
                ++visited[nextNode]; 
                bfsQueue.push(nextNode);
                calcEdges.push(make_pair(node, nextNode));
            }
        }
    }
    
    while(!calcEdges.empty()){
        int pNode =calcEdges.top().first, cNode = calcEdges.top().second;
        calcEdges.pop();
        res += abs(weights[cNode]), weights[pNode] += weights[cNode];
    }
    
    printf("%d", weights[0]?-1:res);
    return 0;
}

5. 라운드로빈

문제 보기

정답 : 3명

손지언

Priority Queue를 이용한 풀이

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

struct Process {
	int PID;
	long long int ExecTime;

	bool operator<(Process _other) const {

		if (this->ExecTime == _other.ExecTime) {
			return this->PID > _other.PID;
		}
		else return this->ExecTime > _other.ExecTime;
		
	}
};
class RR {
private:
	priority_queue<Process> Table;
	vector<int>run;
	vector<int>remainTime;
	long long curTime=0;
	int totallen;
	int len;

public:

	long long int getPID(long long k) {
		Process curP;
		bool found = false;
		long long res;
		long long int clear_iter, prev_iter = 0;
		while (true) {
			curP = Table.top();
			clear_iter = curP.ExecTime;

			if (curTime + (clear_iter - prev_iter) * len > k)
				break;
			else curTime += (clear_iter - prev_iter) * len;
			Table.pop();
			len--;

			prev_iter = clear_iter;

		}
		vector<int>remain;
		while (!Table.empty()) {
			curP = Table.top();
			Table.pop();
			remain.push_back(curP.PID);

		}

		sort(remain.begin(), remain.end());
		res = remain[(k - curTime) % remain.size()];
		return res;

	}
	void getTimes_io() {
		int n,  timeInput;
		long long k,sum = 0;
		cin >> n >> k;
		len = n;
		totallen = n;
		for (int i = 0; i < n; i++) {			
			Process pInput;
			
			cin >> timeInput;
			pInput.PID = i;
			pInput.ExecTime = timeInput;
			sum += timeInput;

			Table.push(pInput);
			run.push_back(i);
			remainTime.push_back(timeInput);
		}
		if (sum <= k) {
			cout << -1;
		}
		else
			cout << getPID(k);
	}

};


int main() {
	RR table;
	table.getTimes_io();
}

제출한 답안 중에는 없었지만 5번은 이외에도 완전히 다른 풀이가 가능합니다.

정산

• 손지언 x2
• 황지원
• 전현준
• 손현수

모범 답안 작성 후 해설 작성시 모범 답안 채택 갯수 시상에 우대합니다(동점자 발생시). 모범 답안 선정되신 분들은 다른 학우분들이 코드를 보고 공부하실 수 있도록 해설 남겨주시면 감사드리겠습니다.

코드에 주석으로 달아주신 분들은 해설을 작성해주신것으로 간주하겠습니다. 물론 추가 해설을 작성해주시면 너무 감사드립니다.

해설은 본 이슈에 계속 달아주세요!

모범 답안 및 해설에 대한 질문이 있으신 분들도 여기에 같이 남겨주시면 좋을 것 같습니다. 슬랙 #dcomding 채널을 이용해주셔도 좋습니다.