8주차 모범 답안

[dhdbstjr98]

개요

• 평균 점수 : 4.2점 (미참여자 제외, 총점 9점)
• 만점자 : 2명

모범 답안

1. 유사회문

문제 보기

정답 : 9명

구희연

투 포인터를 이용한 풀이

def check(s,left,right):
    while left<right:
        if s[left]==s[right]:
            left+=1
            right-=1
        else:
            return False
    return True

def twopointer(s,left,right):
    while left<right:
        if s[left]==s[right]:
            left+=1
            right-=1
        else:
            if check(s,left+1,right) or check(s,left,right-1): #그 전후 원소들은 볼필요가 없다 이미 같으니까!
                return 1
            return 2
    return 0
s = input() 
print(twopointer(s,0, len(s)-1))

2. 색종이 붙이기

문제 보기

정답 : 4명

나혜원

dfs를 이용한 풀이

#include <iostream>
using namespace std;

int paper[10][10];
int colorpaper[5] = { 0,0,0,0,0 };
int answer = 26;

bool is_square(int x, int y, int n)
{
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (paper[x + i][y + j] == 0)
				return false;
		}
	}
	return true;
}

void glue(int x, int y, int count) {
	while (paper[x][y] == 0) {
		y++;
		if (y == 10) {
			x++;
			if (x == 10){
				if (count < answer)
					answer = count;
				return;
			}
			y = 0;
		}
	}
	if (answer <= count)
		return;

	for (int i = 5; i > 0; i--) {
		if (x + i <= 10 && y + i <= 10 && colorpaper[i] < 5 && is_square(x, y, i) == true) {
			for (int j = 0; j < i; j++) {
				for (int k = 0; k < i; k++) {
					paper[x + j][y + k] = 0;
				}
			}
			colorpaper[i]++;
			glue(x, y, count + 1);
			for (int j = 0; j < i; j++) {
				for (int k = 0; k < i; k++) {
					paper[x + j][y + k] = 1;
				}
			}
			colorpaper[i]--;
		}
	}
}

int main() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++)
			cin >> paper[i][j];
	}

	glue(0, 0, 0);

	if (answer > 25)
		answer = -1;

	cout << answer << endl;

	return 0;
}

3. 출튀

문제 보기

정답 : 2명

심규진

pq + 비트마스킹을 이용한 풀이

def solution():
    from heapq import heappop, heappush
    import sys

    input = sys.stdin.readline
    MAX = sys.maxsize
    n,m,k,start,end = map(int,input().split())
    traps = list(map(int,input().split()))
    trap_checker = [-1] * (n + 1)
    for i in range(k):
        trap_checker[traps[i]] = i

    roads = {i:{} for i in range(1,n + 1) }
    reversed_roads = {i:{} for i in range(1,n + 1) }
    for i in range(m):
        p,q,t = map(int,input().split())
        try:
            roads[p][q] = min(t, roads[p][q] )
            reversed_roads[q][p] = min(t, reversed_roads[q][p] )
        except:
            roads[p][q] = t
            reversed_roads[q][p] = t
    # 함정방의 최대 개수가 10개이므로 비트마스크를 써야함.
    # road를 각 함정방의 경우에 수의 따라 다 만들어 놓자. -> 시간 초과의 원인이 이거네
    # 최대가 3000 * 1000 = 3백만
    bit_max = pow(2,k)
    bit_check = [pow(2, i) for i in range(k)]

    visited = [[0] * (n + 1) for i in range(bit_max)]
    findings = []

    # cost, cur_pos, bit_idx
    heappush(findings, (0, start, 0))

    def visit(bit_idx, cur_cost,nxt_pos, cost):
        # 다음 길이 트랩이라면
        if trap_checker[nxt_pos] != -1:
            new_bit_idx = bit_idx ^ bit_check[trap_checker[nxt_pos]]
            if visited[new_bit_idx][nxt_pos]:
                return
            heappush(findings, (cur_cost + cost, nxt_pos, new_bit_idx))
        else:
            if visited[bit_idx][nxt_pos]:
                return
            heappush(findings, (cur_cost + cost, nxt_pos, bit_idx))
    
    def is_reversed(bit_idx,pos):
        if trap_checker[pos] != -1 and bit_idx & bit_check[trap_checker[pos]]:
            return True
        return False
    while findings:

        cur_cost, cur_pos, bit_idx = heappop(findings)
        if visited[bit_idx][cur_pos]:
            continue
        # 종결 조건
        if cur_pos == end:
            return cur_cost
        visited[bit_idx][cur_pos] = 1

        # 이번이 거꾸로 되있다면.
        if trap_checker[cur_pos] != -1 and bit_idx & bit_check[trap_checker[cur_pos]]:
            # 역방향 간선들에 대해
            for nxt_pos in reversed_roads[cur_pos].keys():
                cost = reversed_roads[cur_pos][nxt_pos]
                if is_reversed(bit_idx,nxt_pos):
                    continue
                visit(bit_idx, cur_cost,nxt_pos, cost)
            
            # 역방항에서 정방향 간선으로 갈 수 있는 경우는 얘네가 함정인 경우 뿐

            for nxt_pos in traps:
                try:
                    cost = roads[cur_pos][nxt_pos]
                    if bit_idx & bit_check[trap_checker[nxt_pos]]:
                        visit(bit_idx, cur_cost,nxt_pos, cost)
                except:
                    continue
        else: # 여기가 정방향이면
            for nxt_pos in roads[cur_pos].keys():
                cost = roads[cur_pos][nxt_pos]
                if is_reversed(bit_idx,nxt_pos):
                    continue
                visit(bit_idx, cur_cost,nxt_pos, cost)
            for nxt_pos in traps:
                try:
                    cost = reversed_roads[cur_pos][nxt_pos]
                    if bit_idx & bit_check[trap_checker[nxt_pos]]:
                        visit(bit_idx, cur_cost,nxt_pos, cost)
                except:
                    continue
    return -1
print(solution())

정산

• 구희연
• 나혜원
• 심규진

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

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

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

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