BOJ 1343. [Silver5] 폴리오미노

[hojongs]

Problem link

https://www.acmicpc.net/problem/1343

Problem abstraction

문제의 핵심을 요약한다. 체계적인 문제 접근을 위해, 문제를 추상화한다

적합한 자료구조를 생각한다

Design(Plan) algorithm

# 1

---
# 2

---
# 3

Algorithm idea

추상화한 문제 이해를 기반으로 알고리즘의 대략적인 구현 계획을 서술한다

Pseudo-code

idea를 수도 코드로 작성해본다

Validate algorithm

알고리즘의 유효 여부를 구현 전에 검증한다

예제 입력을 수도 코드로 계산해보고, 놓친 알고리즘 오류가 있는지 확인한다

Impl

import sys

readl = sys.stdin.readline

s = readl().rstrip()
result = []

def f():
    """
    이전 X 위치 = 첫 X 위치를 찾음 (처음이 점일 수도 있음)
    순회
    - X가 끝날 때까지 전진
    - (이전 X 위치 ... 현재 X 위치)에 대해 채운다
      - AAAA를 채우고, +4 index에서 재귀 호출
      - 이전의 채움 결과가 -1이면:
        - BB를 채우고, +2 index에서 재귀 호출
        - 이 채움 결과도 -1이면 -1 출력 후 종료
    이후에 구현하면서 조금씩 보완
    """
    i = 0
    while i < len(s):
        cnt = 0
        while i < len(s) and s[i] == '.':
            i += 1
            cnt += 1
        result.append("." * cnt)
        x_start = i
        while i < len(s) and s[i] == 'X':
            i += 1
        if fill(x_start, i) == -1:
            return -1
    return ''.join(result)

def fill(si, ei_exclusive):
    if si > ei_exclusive:
        return -1
    elif si == ei_exclusive:
        return 0
    else:
        result.append("AAAA")
        if fill(si+4, ei_exclusive) == -1:
            result.pop()
            result.append("BB")
            if fill(si+2, ei_exclusive) == -1:
                result.pop()
                return -1
            else:
                return 0
        else:
            return 0

print(f())

Self-feedback

구조적 접근: 문제를 추상화하여 구조적으로 접근했는가?

구현하면서 보완하지 말자. 계획을 최대한 세운 후 구현하자.

사고력: 알고리즘을 완전히 이해했는가? (충분한 사고력을 가졌는가?)

replace idea

https://www.acmicpc.net/source/37193337

split + 길이를 4로 나누고 2로 나눈 값만큼 AAAA, BB를 붙이는 idea

https://www.acmicpc.net/source/37212464

좀더 간단한 아이디어들이 있다

첫 번째 아이디어가 아니라, 다양한 후보 아이디어들을 생각해본 후 선택하자

구현력: 알고리즘을 신속, 정확하게 구현했는가?