4주차 모범 답안

[dhdbstjr98]

개요

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

모범 답안

1. 인형뽑기

문제 보기

정답 : 11명

장예원

stack, queue를 이용한 풀이

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

int main() {
	int n, k, num;
	queue<int> moves;
	stack<int> stk;

	cin >> n >> k;
	vector<queue<int>> board(n + 1);

	for (int i = 0; i < k; i++)
	{
		cin >> num;
		moves.push(num);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> num;
			if (num) board[j].push(num);
		}
	}

	int top, total = 0;
	while (!moves.empty()) {
		num = moves.front();
		moves.pop();
		if (!board[num].empty()) {
			if (stk.empty()) top = 0;
			else top = stk.top();

			if (top == board[num].front() && !stk.empty()) {
				stk.pop();
				total += 2;
			}
			else {
				stk.push(board[num].front());
			}
			board[num].pop();
		}
	}
	cout << total;
	return 0;
}

2. 동아리방

문제 보기

정답 : 10명

나혜원

greedy를 이용한 풀이

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

struct Times
{
	int start;
	int end;
};

bool schedule(Times x, Times y) {
	if (x.end != y.end)
		return x.end < y.end;
	else
		return x.start < y.start;
}

int main()
{
	int n;
	cin >> n;

	Times* times = new Times[n];
	for (int i = 0; i < n; i++) {
		cin >> times[i].start >> times[i].end;
	}
	sort(times, times + n, schedule);

	int count = 0;
	int end = -1;

	for (int i = 0; i < n; i++) {
		if (times[i].start >= end) {
			count++;
			end = times[i].end;
		}
	}

	cout << count << endl;

	return 0;
}

3. 로봇

문제 보기

정답 : 5명

손현수

bfs를 이용한 풀이

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

#define pii pair<int, int>

int n, board[102][102], temp, robotBoard[102][102][2], dx[]={1,-1,0,0}, dy[]={0,0,1,-1};
queue<pair<pii, pii>> bfsQueue;

int main()
{
    scanf("%d",&n);
    for(int row=1; row<=n; ++row)
        for(int col=1; col<=n; ++col){
            scanf("%d",&temp);
            //board에서 0을 장애물로 이용하기 위해 입력받은 값에서 0->1, 1->0으로 바꿔서 저장함
            //이후로 1이 빈칸, 0이 장애물이 됨
            //이 방법을 쓰면 저장되지 않은 board의 모든 칸이 장애물로 인식되어 따로 벽 처리해주지 않아도 됨
            board[row][col] = !temp;
        }
    
    //robotBoard는 모두 0으로 초기화되어 있기 때문에 초기값과 방문값에 차이를 두기 위해 첫 좌표를 1로 설정함
    //앞으로 0이면 방문하지 않은 좌표, 0이 아니면 방문했던 좌표가 됨
    robotBoard[1][1][0] = 1;
    bfsQueue.push(make_pair(make_pair(1,1),make_pair(1,2)));
    
    //로봇의 왼쪽/위쪽 팔이 있는 좌표가 값을 저장할 좌표가 됨
    //따라서 bfsQueue에 새로운 좌표를 넣을 때는 항상 first가 왼쪽/위쪽 팔의 좌표가 되도록 넣어야 함
    while(!bfsQueue.empty()){
        //mode는 0일 때 가로, 1일 때 세로를 뜻함. lu = left/up, rd = right/down, n = next를 뜻함
        pii luPos = bfsQueue.front().first, rdPos = bfsQueue.front().second;
        int lux = luPos.first, luy = luPos.second, rdx = rdPos.first, rdy = rdPos.second,
            mode = luy == rdy, val = robotBoard[lux][luy][mode]+1;
        bfsQueue.pop();
        
        //cnt 0:아래쪽이동, 1:위쪽이동, 2:오른쪽이동, 3:왼쪽이동
        for(int cnt=0; cnt<4; ++cnt){
            int lunx = lux + dx[cnt], luny = luy + dy[cnt],
                rdnx = rdx + dx[cnt], rdny = rdy + dy[cnt];
            pii lunPos = make_pair(lunx,luny), rdnPos = make_pair(rdnx,rdny);
            
            //로봇이 이동할 좌표가 모두 빈칸(=1)이라면
            if(board[lunx][luny] && board[rdnx][rdny]){
                
                //상하좌우용 코드
                //다음 좌표를 방문하지 않았다면 방문값을 저장하고 bfsQueue에 넣음
                if(!robotBoard[lunx][luny][mode]){
                    robotBoard[lunx][luny][mode] = val;
                    bfsQueue.push(make_pair(lunPos,rdnPos));
                }
            
                //회전용 코드
                //로봇이 가로모드일 때 상/하로 이동할 수 있으면 좌상,우상/좌하,우하로 회전할 수 있음
                //로봇이 세로모드일 때 좌/우로 이동할 수 있으면 좌상,좌하/우상,우하로 회전할 수 있음
                //cnt<=1 : 상하이동, cnt>1 : 좌우이동, !mode : 세로모드, mode : 가로모드
                if(cnt/2 == mode){ // == (cnt>1 && mode) || (cnt<=1 && !mode)
                    if(cnt%2){ //(cnt, mode) : (1,0), (3,1)
                        
                        //로봇이 위쪽/왼쪽으로 이동했을 때는 원래 좌표보다 이동한 좌표가 더 작기 때문에 이동한 좌표를 기준으로 방문 여부를 확인함
                        if(!robotBoard[lunx][luny][!mode]){
                            robotBoard[lunx][luny][!mode] = val;
                            bfsQueue.push(make_pair(lunPos, luPos));
                        }
                        if(!robotBoard[rdnx][rdny][!mode]){
                            robotBoard[rdnx][rdny][!mode] = val;
                            bfsQueue.push(make_pair(rdnPos, rdPos));
                        }
                    }
                    else{ //(cnt,mode) : (0,0), (2,1)
            
                        //로봇이 아래쪽/오른쪽으로 이동했을 때는 원래 좌표가 이동한 좌표보다 더 작기 때문에 원래 좌표를 기준으로 방문 여부를 확인함
                        if(!robotBoard[lux][luy][!mode]){
                            robotBoard[lux][luy][!mode] = val;
                            bfsQueue.push(make_pair(luPos, lunPos));
                        }
                        if(!robotBoard[rdx][rdy][!mode]){
                            robotBoard[rdx][rdy][!mode] = val;
                            bfsQueue.push(make_pair(rdPos, rdnPos));
                        }
                    }
                    //if-else 없이 min,max 처리하면 코드 수가 줄어들지만, 보기 힘들까봐 min,max처리는 하지 않음
                }
            }
        }
    }
    
    //(n,n)에 로봇이 걸치는 가로 좌표(n,n-1), 세로 좌표(n-1,n) 중 더 작은 값을 출력함
    //0이면 10억을 반환해서 선택되지 않도록 하고 로봇의 시작점을 1로 잡았으니 1을 빼줌
    printf("%d",min(robotBoard[n][n-1][0]?robotBoard[n][n-1][0]:1<<30,robotBoard[n-1][n][1]?robotBoard[n-1][n][1]:1<<30)-1);
        
    return 0;
}

4. 경사로

문제 보기

정답 : 6명

전현준

N, L = map(int, input().split())
board = [list(map(int, input().split())) for i in range(N)]

count = N*2
for way in board + [[board[j][i] for j in range(N)] for i in range(N)]:
    height = way[0]
    for i, h in enumerate(way):
        if 2 <= abs(height-h):
            count -= 1
            break
        elif 1 <= abs(height - h):
            if h < height and i+L <= N and set(way[i:i+L]) == {h}:
                height -= 1
                way[i:i+L] = [h+0.5]*L
            elif h > height and i-L >= 0 and set(way[i-L:i]) == {height}:
                height += 1
                way[i-L:i] = [h-0.5]*L
            else:
                count -= 1
                break

print(count)

5. 이진 탐색 트리

문제 보기

정답 : 3명

손현수

union-find를 이용한 풀이

//solving with union-find, backtracking : 80ms
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;

#define max(a,b) (a>b?a:b)

int n, v, left, right, leftGroup[100002], rightGroup[100002], disFromRoot[100002];
long long res;
stack<int> vStack;
stack<pair<int,pair<int,int>>> rangeStack;

int findLeft(int num){
    if(leftGroup[num] == num) return num;
    else return leftGroup[num] = findLeft(leftGroup[num]);
}

int findRight(int num){
    if(rightGroup[num] == num) return num;
    else return rightGroup[num] = findRight(rightGroup[num]);
}

//알고리즘 배경
//이진트리의 빠른 삽입은 삽입하고자 하는 값과 가장 가까이에 있는 값 중 비어있는 가지에 넣는 것이다.
//예시로 이진트리 안에 1 6 4 2 순으로 넣었다면 5를 넣을 때는 4와 6 중에 비어있는 가지인 4오른쪽에 넣고(6왼쪽에는 4가 들어가 있다)
//5가 들어간 후 3을 넣는다면 2와 4 중에 비어있는 가지인 2의 오른쪽에 넣는 것이다.(4왼쪽에는 2가 들어가 있다)
//여기서 문제는 '삽입하고자 하는 값과 가장 가까운 두 수를 어떻게 얻을 것인가' 이다.
//만약 O(1)만에 값을 얻고자 가장 가까운 두 수를 저장하는 배열을 만들었다고 해보자.
//초기에는 배열1은 모드 0으로 초기화 되어 있고, 배열2는 n+1로 초기화 되어 있을 것이다.
//하지만 값을 삽입한 뒤, 배열1은 [값,n]구간을 값으로 업데이트하고, 배열2는 [1,값]구간을 값으로 업데이트하면 시간적 손실이 굉장히 많이 나게 된다.
//여기서 두 배열은 모든 값을 삽입한 후 (배열[값] == 값) 이라는 특성을 이용해 백트래킹을 진행한다.
int main()
{
    scanf("%d",&n);
    for(int cnt=0;cnt<n;++cnt){
        scanf("%d",&v);
        vStack.push(v);
    }
    
    //union-find 초기 세팅, 여기서 자기자신을 가리킨다는 건 이진트리에 삽입되어 있음을 의미함
    for(int cnt=0;cnt<=100001;++cnt)
        leftGroup[cnt] = rightGroup[cnt] = cnt;
    
    while(!vStack.empty()){
        v = vStack.top(); vStack.pop();
        
        //자신과 가장 가까이에 있는 왼쪽값과 오른쪽 값을 구함
        left = findLeft(v-1), right = findRight(v+1);
        
        //자신은 이제 트리에 없는 값이 될 것이므로 자신을 가리키지 않도록 왼쪽과 오른쪽 값을 저장함
        leftGroup[v] = left, rightGroup[v] = right;
        
        //재귀함수 스택 오버플로우 방지용
        //[v,right-1], [left+1,v] 구간에 있는 모든 값은 모두 이진트리에 없기 때문에 이를 이용해 배열을 업데이트 함
        findLeft(right-1), findRight(left+1);
        
        //삽입할 값과 가장 가까운 왼쪽값, 오른쪽값을 스택에 저장함
        rangeStack.push(make_pair(v,make_pair(left,right)));   
    }
    
    while(!rangeStack.empty()){
        v = rangeStack.top().first, left = rangeStack.top().second.first, right = rangeStack.top().second.second;
        rangeStack.pop();
        
        //구간 중 루트와 거리가 더 먼 노드를 채택해 v노드에 기록하고 result에 높이를 반영함
        res+=(disFromRoot[v] = max(disFromRoot[left], disFromRoot[right])+1)-1;
        
        printf("%lld\n",res);
    }
    return 0;
}

송용우

map과 binary search를 이용한 풀이

/*
이진 탐색 트리
N의 크기는 10만
C의 값은 곧 랭크 누적
매번 insert 함수를 수행한다면
시간복잡도는 O(N)이므로 수행 시간을 보장할 수 없다.
또한 최악의 경우 편향 이진 트리가 될 수 있어 O(N^2)
이진탐색트리 삽입 원리를 이해하자
*/

#include <iostream>
#include <map>
#include <utility>
#include <algorithm>

using namespace std;

map<int, int> m;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int n;
	cin >> n;
	long long C = 0;
	int depth;
	
	/*
	최대 최소 값 처리 테크닉
	*/
	m.insert({0,-1});
	m.insert({100005, -1});
	
	for(int i = 0; i < n; i++){
		int num;
		cin >> num;
		auto up_iter = m.upper_bound(num);
		auto low_iter = up_iter;
		--low_iter;//후위 연산자를 사용하면 이전 값을 반환하기 때문에 임시 객체가 생겨 성능이 낮아진다고 함.
		depth = max(up_iter->second, low_iter->second) + 1;
		m.insert({num, depth});
		C += depth;
		cout << C << '\n';
	}
	return 0;
}

심규진

Red-Black Tree를 이용한 풀이

중간에 제출한 답안이지만 성공 이력이 있고 의미가 있는 답변이라 생각해 추가합니다. 본 테스트 환경에서는 성공하지만 원본 문제(백준) 에서는 언어적 한계로 timeout됩니다.

import sys
input = sys.stdin.readline
# 참고글 : https://www.crocus.co.kr/641
# 참고글 : https://lsh424.tistory.com/73
# 참고글 : https://zeddios.tistory.com/237
class Node:
    def __init__(self, data):
        self.data = data
        self.left = self.right = self.parent = None
        self.color = 'R'
        

class RedBlackTree:
    def __init__(self):
        self.root = None
    
    def find_gp_node(self,node):
        try:
            return node.parent.parent
        except:
            return None 
    def find_uncle_node(self,node):
        grandparent_node = self.find_gp_node(node)
        try:
            if node.parent == grandparent_node.left:
                return grandparent_node.right
            else:
                return grandparent_node.left
        except:
            return None 
    
        
        
    def rotate_left(self,node):
        c = node.right
        p = node.parent
        # node와 c 위치 변경
        try:
            c.left.parent = node
        except:
            pass
        node.right = c.left
        node.parent = c
        c.left = node
        c.parent = p
        
        # 만약 변경해 올라간 위치가 root라면
        if c.parent == None:
            self.root = c
        # 아니라면 node의 원래 위치에 c 등록
        else:
            if p.left == node:
                p.left = c
            else:
                p.right = c
                
    def rotate_right(self,node):
        c = node.left
        p = node.parent
    
        try:
            c.right.parent = node
        except:
            pass
            
        node.left = c.right
        node.parent = c
        c.right = node
        c.parent = p
        
        if c.parent == None:
            self.root = c
        else:
            if (p.right == node):
                p.right = c
            else:
                p.left = c
    
    # case1. 루트 노드는 항상 블랙  
    # case2. 부모 노드가 블랙이면 회전, 색변환등 수행 필요 x, 하지만 빨강색이라면 case3 수행
    def insert_case1(self,node):
        try:
            if node.parent.color == 'R':
                self.insert_case3(node)
        except:
            node.color = 'B'
            
    
    # case3. 부모노드, 삼촌노드 모두 빨강이라면 색변환 수행, 아닐경우 case4로 이동
    def insert_case3(self,node):
        uncle = self.find_uncle_node(node)
    
        if (uncle != None and uncle.color == 'R'):
            node.parent.color = 'B'
            uncle.color = 'B'
            grandparent = self.find_gp_node(node)
            grandparent.color = 'R'
            self.insert_case1(grandparent)
        else:
            self.insert_case4(node)      
    # case4,5 회전 수행
    def insert_case4(self,node):
        
        grandparent = self.find_gp_node(node)
    
        if(node == node.parent.right and node.parent == grandparent.left):
            self.rotate_left(node.parent)
            node = node.left
        elif (node == node.parent.left and node.parent == grandparent.right):
            self.rotate_right(node.parent)
            node = node.right
    
        node.parent.color = 'B'
        grandparent.color = 'R'

        if (node == node.parent.left):
            self.rotate_right(grandparent)
        else:
            self.rotate_left(grandparent) 
        
    # 삽입
    def insert(self, data):
        node, bigger_min, smaller_max = self.insert_value(data)
        self.insert_case1(node)
        return bigger_min, smaller_max
    # 재귀에서 while로 바꾸고 항상 한개의 데이터만 입력받게 바꿈.
    def insert_value(self, data):
        if self.root == None:
            self.root = Node(data)
            return self.root, None, None
        node = self.root
        parent_node = smaller_max = bigger_min=  None
        # min max 안달아도 될 것 같긴함.
        while node != None:
            parent_node = node
            if data < node.data:
                bigger_min = node.data
                node = node.left
            else:
                smaller_max = node.data
                node = node.right
        node = Node(data)
        node.parent = parent_node
        if data < parent_node.data:
            parent_node.left = node
        else:
            parent_node.right = node
            
        return node, bigger_min, smaller_max
class BinaryNode:
    def __init__(self, depth):
        self.depth = depth
        self.right = self.left = None
'''
def check(node):
    if not node.left  == None : check(node.left)
    if node.parent != None:
        print('key: ', node.data, 'parents: ', node.parent.data, 'color: ', node.color, end = '\n')
    else:
        print('key: ', node.data, 'parents: ', node.parent, 'color: ', node.color, end = '\n')
    if not node.right == None : check(node.right)
'''
def solve():
    N = int(input())
    values = list(map(int, input().split()))
    rb_tree = RedBlackTree()
    tree = [0] * (N + 1)
    result_str = ""
    result = 0
    for value in values:
        bigger_min, smaller_max = rb_tree.insert(value)
        depth = 1
        try:
            if tree[bigger_min].left == None:
                tree[bigger_min].left = value
                depth = tree[bigger_min].depth + 1
        except:   
            pass
        
        try:
            if tree[smaller_max].right == None:
                tree[smaller_max].right = value
                depth = tree[smaller_max].depth + 1
        except:   
            pass

        tree[value] = BinaryNode(depth)
        result += depth - 1
        result_str += str(result) + '\n'
    print(result_str)
solve()

정산

• 손현수 x2
• 장예원
• 나혜원
• 전현준
• 송용우
• 심규진

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

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

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

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