3주차 모범 답안

[dhdbstjr98]

개요

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

모범 답안

1. 전공책 빌리기

문제 보기

정답 : 14명

장재훈

set을 이용한 풀이

n, k = map(int, input().split())
l = len(list(set(map(int, input().split()))))
    
print(l if k > l else k)

2. 외주

문제 보기

정답 : 14명

최성원

DP를 이용한 풀이

#dp(n) = max(dp(n), dp(i)+p(i))
#dp(n) : n일까지의 수익
#n일 이전에 받을 수 있는 모든 경우중 가장 큰값으로 갱신

n = int(input())
table = []
dp = []
answer = 0
for i in range(n):
    t, p = map(int, input().split())
    table.append((t, p))
    dp.append(p)

#날짜를 초과하지 않는 선에서 단순히 수익만 계산
for i in range(1, n):
    for j in range(i):
        if j + table[j][0] <= i:
            dp[i] = max(dp[i], dp[j]+table[i][1])
            #dp(i) = max(i일까지의 수익, j일까지의 수익 + i일의 수익)

#여기서 실제 그 외주를 맡았을 때 할 수 있는지 검사
for i in range(n):
    if i+table[i][0] <= n:
        if answer < dp[i]:
            answer = dp[i]
print(answer)

장예원

DFS를 이용한 풀이

n ≤ 15 이므로 dfs로 풀어도 시간 안에 해결 가능

#include <iostream>
#include <vector>
using namespace std;

void DFS(vector<vector<int>>& table, int index, int total, int& max) {
	int size = table.size();
	for (int i = index; i < size; i++)
	{
		if (i + table[i][0] <= size)
		{
			total += table[i][1];
			DFS(table, i + table[i][0], total, max);
			total -= table[i][1];
		}
	}
	if (total > max) max = total;
}

int main() {
	int n, t, p, total = 0, max = 0;
	vector<vector<int>> table;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> t >> p;
		table.push_back({ t, p });
	}
	DFS(table, 0, 0, max);
	cout << max;
	return 0;
}

3. 셔틀버스

문제 보기

정답 : 11명

전현준

n, t, m, k = map(int, input().split())
passengers = sorted([(lambda x: int(x[0])*60 + int(x[1]))(input().split()) for i in range(k)], reverse=True)

for time in range(9*60 + 0, 23*60 + 59, t)[:n]:
    bus = [passengers.pop() for i in range(m) if passengers and passengers[-1] <= time]
    
if len(bus) == m:
    time = bus[-1] - 1

print(time//60, time%60)

4. 다리 만들기

문제 보기

정답 : 4명

손현수

DFS와 MST를 이용한 풀이

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

int campus[11][11], n, m;
vector<pair<int, pair<int, int>>> bridges;

//2차원 배열의 유효한 위치인 지 확인하는 함수
bool canGotoPos(int x, int y){
	return 0<=x && x<n && 0<=y && y<m;
}

//dfs 건물, 다리 탐색용
int dx[]={1,-1,0,0}, dy[]={0,0,1,-1}, bCnt;
void dfs(int x, int y, int mode, int val){
	
	//건물 탐색용
	if(mode == -1){
		campus[x][y] = val;
		
		//4방향으로 뻗어가면서 더 이어진 부분이 있는 지 확인함
		for(int cnt=0;cnt<4;++cnt){
			int nx = x+dx[cnt], ny = y+dy[cnt];
			if(canGotoPos(nx, ny) && campus[nx][ny] == -1)
				dfs(nx, ny, mode, val);
		}
	}
	
	//다리 탐색용
	else{
		int nx = x+dx[mode], ny = y+dy[mode];
		if(canGotoPos(nx, ny)){
			
			//다음 지점이 빈 공간이면 한칸 더감
			if(campus[nx][ny] == 0)
				dfs(nx, ny, mode, val+1);
			
			//다음 지점이 자기 건물이 아니면서 거리가 1보다 크면 벡터에 저장. min,max는 나중에 중복된 다리를 없애기 위함임
			else if(campus[nx][ny] != bCnt && val>1)
				bridges.push_back(make_pair(val, make_pair(min(bCnt, campus[nx][ny]), max(bCnt, campus[nx][ny]))));
			
		}
	}
}

//union-find 함수
int group[7];
int findGroup(int bNum){
	if(bNum == group[bNum]) return bNum;
	return group[bNum] = findGroup(group[bNum]);
}

 
int main() {
	scanf("%d%d",&n,&m);
	for(int nCnt = 0; nCnt<n; ++nCnt)
		for(int mCnt = 0; mCnt<m; ++mCnt){
			scanf("%d",&campus[nCnt][mCnt]);
			//건물의 번호가 1번부터 시작하므로 건물의 존재여부와 건물번호에 차이를 두기 위해 건물의 존재여부는 -1로 저장함
			campus[nCnt][mCnt] = -campus[nCnt][mCnt];
		}
	
	//dfs를 통해 건물 특정짓기
	int totalBuilding = 0;
	for(int nCnt = 0; nCnt<n; ++nCnt)
		for(int mCnt = 0; mCnt<m; ++mCnt)
			
			//방문한 지점에 번호가 매겨지지 않은 건물이 있으면 건물에 번호를 붙여줌
			if(campus[nCnt][mCnt] == -1) 
				dfs(nCnt, mCnt, -1, ++totalBuilding);
			
	
	//dfs를 통해 각 건물을 연결하는 다리 만들기. bCnt는 dfs()에서도 사용됨
	for(bCnt = 1; bCnt<=totalBuilding; ++bCnt)
		for(int nCnt = 0; nCnt<n; ++nCnt)
			for(int mCnt = 0; mCnt<m; ++mCnt)
				
				//방문한 지점이 건물이면 한 방향으로 다리를 놓아봄
				if(campus[nCnt][mCnt] == bCnt)
					for(int cnt=0; cnt<4; ++cnt)
						dfs(nCnt, mCnt, cnt, 0);
				
	
	//unoin-find 초기 세팅
	for(int cnt=1; cnt<=6; ++cnt)
		group[cnt] = cnt;
	
	//중복된 다리 제거
	sort(bridges.begin(), bridges.end());
	bridges.erase(unique(bridges.begin(), bridges.end()),bridges.end());
	
	//최소 스패닝 트리를 이용한 간선 채택
	int matchCnt=1, result=0;
	for(int cnt=0; cnt<bridges.size(); ++cnt){
		int val = bridges[cnt].first, x = bridges[cnt].second.first, y = bridges[cnt].second.second;
		
		//채택된 두 건물이 서로 다른 그룹이면 다리를 선택함
		if(findGroup(x) != findGroup(y))
			group[findGroup(y)] = findGroup(x), ++matchCnt, result+=val;
		
		//모든 건물이 한 그룹으로 묶였으면 다리 선택을 그만둠.
		if(matchCnt == totalBuilding) break;
	}
	
	//모든 건물이 하나로 묶였으면 result, 아니면 불가능하다는 뜻이므로 -1을 출력
	printf("%d",matchCnt==totalBuilding?result:-1);

	return 0;
}

5. 히스토그램

문제 보기

정답 : 3명

손현수

stack을 이용한 풀이

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

#define pii pair<int, int>

int n, h, result;

//histograms에는 항상 오름차순 높이만 존재하게끔 만듦 (뽑을 때는 내림차순으로 나옴)
stack<pii> histograms;

int main() {
	scanf("%d",&n);
	for(int cnt=0;cnt<n;++cnt){
		scanf("%d",&h);
		
		int possiblePtr = cnt;		
		while(!histograms.empty() && h<=histograms.top().first){
			pii histogram = histograms.top(); histograms.pop();
			
			//현재 높이에서 가능한 넓이와 result를 비교함
			result = max(result, h*(cnt-histogram.second+1));
			
			//스택에 있던 first는 현재 높이 h에서는 불가능하므로 h이전 위치까지의 넓이와 result를 비교함
			//이게 가능한 이유는 histograms가 오름차순으로 들어가 있기 때문에 넓이가 보장됨.
			result = max(result, histogram.first*(cnt-histogram.second));
			
			//h보다 크거나 같은 높이값이기 때문에 second(=first 높이의 시작점)부터 최소 h만큼의 높이를 보장함
			possiblePtr = histogram.second;
		}
		histograms.push(make_pair(h,possiblePtr));
	}
	
	//마지막으로 스택에서 빠지지 않은 (높이,시작점)들을 빼면서 최대값을 갱신함.
	while(!histograms.empty()){
		pii histogram = histograms.top(); histograms.pop();
		result = max(result, histogram.first*(n-histogram.second));
	}
	
	printf("%d",result);
	return 0;
}

송용우

분할 정복을 이용한 풀이

/*
모든 경우의 수를 탐색?
N^2이므로 10000000000 백억이므로 해결 불가
분할 정복 활용을 활용하자!
사각형이 왼쪽, 오른쪽, 걸쳐있을 케이스 고려
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> heights;

//left ~ right까지 찾을 수 있는 사각형 중 가장 큰 사각형 반환
int search(int left, int right){
	if(left == right){//base
		return heights[left];
	}
	int mid = (left + right) / 2;
	//왼쪽, 오른쪽
	int ret = max(search(left, mid), search(mid+1, right));
	
	
	//걸쳐있을 케이스
	int height = min(heights[mid], heights[mid+1]);
	ret = max(ret, height * 2);
	int l_idx = mid;
	int r_idx = mid + 1;
	while(left < l_idx || r_idx < right){
		if(r_idx < right && (l_idx == left || heights[l_idx - 1] < heights[r_idx + 1])){
			r_idx++;
			height = min(height, heights[r_idx]);
		}else{
			l_idx--;
			height = min(height, heights[l_idx]);
		}
		
		ret = max(ret, height * (r_idx - l_idx + 1));
	}
	return ret;
}

int main(){
	cin >> N;
	heights.resize(N);
	for(int i = 0; i < N; i++){
		cin >> heights[i];
	}
	cout << search(0 , N-1);
	return 0;
}

정산

• 손현수x2
• 장재훈
• 최성원
• 장예원
• 전현준
• 송용우

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

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

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

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

[Untaini]

5번의 알고리즘을 좀 더 쉽게 이해하기 위한 베이스를 알려드리겠습니다.

사각형을 계산하기 위해서는 임의의 한 막대를 기준으로 높이가 양쪽으로 얼마나 뻗어나갈 수 있는 지를 알아야 합니다.
그 지점은 처음으로 자기 막대보다 높이가 낮아지는 지점이고 그러면 그 지점을 어떻게 알아낼 것인가가 알고리즘이 될 것입니다.

다음부터는 코드와 같이 보시면 이해가 더 잘될 겁니다.
오른쪽에서 끝나는 지점은 쉽게 단정지을 수 있습니다. 스택에서 빠지는 순간이죠. 스택에서 빠지는 높이들은 이미 최대까지 온 것이고 그 지점을 기점으로 사각형 계산을 합니다.
왼쪽에서 시작하는 지점은 생각하기 어려울 수 있는데요. 이 역시 스택에서 빠지는 순간을 이용해서 구할 수 있습니다. 스택에서 빠지는 높이들은 현재 높이보다 높아서 빠집니다. 하지만 이를 다르게 생각해보면 스택에서 빠지는 높이들의 시작점은 현재 높이의 시작점으로도 이용할 수 있다는 얘기입니다. 그래서 그 사실을 가지고 시작점을 갱신하면 현재 막대의 왼쪽 시작점을 구할 수 있게 됩니다.

스택을 이용한 알고리즘의 아이디어를 드리고자 dcomding-forum에도 힌트를 살짝 드렸었는데요. 스택/정렬된 값을 이용해서 원하는 결과를 도출하는 방식이 5번 문제와 비슷해서 힌트로 사용했었는데 도움이 되셨을 지 모르겠습니다

혹시 궁금한 사항이 있으시면 슬랙이나 이슈를 달아주시면 답변해드리겠습니다