[Python]백준 2590 색종이

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

2590번: 색종이

<알고리즘을 아직 안배워서, 관련내용은 없습니다>

반례 입력값 찾다가 뒤질뻔했다. 결국 못찾아서 코드뒤적거리면서 고쳤다...절때 반례 입력값 찾으려 시도하지말것...
23.11.22 아래 풀이가, 그리디한(큰 색종이부터 넣기) 풀이라고 합니다.

백준이 오류난줄알고 몇번씩 제출해봤다...

문제 분석

이건 저번 보석문제보다 더욱 분석할게 없다. 정사각형(6x6)칸에 색종이 안겹치게 겹치면 된다.
색종이는 1x1~6x6정사각형 크기로 이루어져있다. 한줄씩 띄어서, 순서대로 1x1~6x6 갯수를
입력받고, 정사각형 칸 수를 출력하면된다.
 

해결과정

아이디어:
1. 6x6색종이는 의심의 여지없이 정사각형 1개 추가한다. 남는칸도없이 맞아떨어짐.
2. 5x5색종이도 의심의 여지없이 정사각형 1개 추가한다. 남는칸에는 1x1만 들어갈 수 있음.
3. 4x4색종이도 의심의 여지없이 정사각형 1개 추가한다. 남는칸에 2x2가 5개 들어갈 수 있음(1x1도 가능)
4. 3x3색종이도 의심의 여지없이 정사각형 1개 추가한다. 그러나, 정사각형 한개에 3x3색종이 4개까지 들어간다.

남는 칸은 1x1색종이만 배치 가능. 가장 중요한건, 3x3색종이가 0~3개일때의 '1x1넣을 수 있는 여유분'이 다 다르다. 따라서 경우를 나눠서 계산해줘야 함.
5. 이제2x2와 1x1를 배치해주면 된다. 

(정말 중요!)

2x2를 비집고 넣을 수 있는 여유분(3번에서 구함)에 먼저 2x2 색종이 배치한다. 이때, 색종이가 남는경우와, 비집고 넣을 수 있는 자리가 남는경우가 있다. 전자의 경우는 새로 정사각형을 마련해줘야하고, 후자의 경우는 남는 비집고넣는 칸을 1x1 들어갈 수 있는 공간으로 보내주면 된다.
 
이렇게 큰 색종이부터 넣어야지 배치에 신경을 안써도 된다. 1x1을 먼저넣어버리면, 배치에 신경을써야해서(2x2넣을 수 있는 자리에 1x1을 넣을것인가 말것인가 등) 한번 더 생각해주어야한다.

#1~6까지 색종이 갯수 파악
a1,a2,a3,a4,a5,a6=[int(input()) for _ in range(6)]
count=(a3//4+1)+a4+a5+a6#3 4 5 6은 무조건 1장씩 필요함. 이후 남는칸에 12들어가는지 확인 후 추가
#남는칸이 2x2인지 1x1인지, 몇개인지 파악
remain22=a4*5#22가 되는 칸의 최소단위갯수(2x2몇칸인지)
remain11=a5*11#11가 되는 칸의 최소단위갯수(1x1몇칸인지)
remain33=4-a3%4#33가 되는 칸의 최소단위갯수(3x3몇칸인지)
must11=remain11#11만가능한칸
if a3%4==0:#3x3가 0개거나 4개면, 남는33은 없음
    remain33=0
    count-=1
#남는3x3 2x2칸에 a2넣을 수 있나 확인,이후 1x1넣기, 부족하면 count 추가
#남는3x3이 3개일때, 2개일때, 1개일때에 따라 전부 달라짐
#22만 다 넣으면, 어차피 마지막에 넣을건 11이므로, 22들어갈수있는칸이든 뭐든 11가능칸으로 체크
if remain33==3:
    remain33_22=5#33으로이뤄진빈칸에 22가 최대5개까지들어갈수있음
    a2=remain33_22-a2
    if a2<0:
        must11+=7
        a2=-a2#2x2남은갯수
        a2=remain22-a2#22되는칸에 넣기
        if a2<0:#칸이부족해서, 1칸추가
            a2=-a2
            must11+=36-a2%9*4
            count=count+a2//9+1
            if a2%9==0:
                must11-=36
                count-=1
        else:#22칸에 22넣고 남은경우, 이때 a2는 남은a2가아니다
            must11+=a2*4
    else:#33칸에 22넣고 남은경우, 이때 a2는 남은a2갯수가 아니다
        must11+=7+a2*4
        must11+=remain22*4
elif remain33==2:
    remain33_22=3
    a2=remain33_22-a2
    if a2<0:
        must11+=6
        a2=-a2#2x2남은갯수
        a2=remain22-a2#22되는칸에 넣기
        if a2<0:#칸이부족해서, 1칸추가
            a2=-a2
            must11+=36-a2%9*4
            count=count+a2//9+1
            if a2%9==0:
                must11-=36
                count-=1
        else:#22칸에 22넣고 남은경우, 이때 a2는 남은a2가아니다
            must11+=a2*4
    else:#33칸에 22넣고 남은경우, 이때 a2는 남은a2갯수가 아니다
        must11+=6+a2*4
        must11+=remain22*4        
elif remain33==1:
    remain33_22=1
    a2=remain33_22-a2
    if a2<0:
        must11+=5
        a2=-a2#2x2남은갯수
        a2=remain22-a2#22되는칸에 넣기
        if a2<0:#칸이부족해서, 1칸추가
            a2=-a2
            must11+=36-a2%9*4
            count=count+a2//9+1
            if a2%9==0:
                must11-=36
                count-=1
        else:#22칸에 22넣고 남은경우, 이때 a2는 남은a2가아니다
            must11+=a2*4
    else:#33칸에 22넣고 남은경우, 이때 a2는 남은a2갯수가 아니다
        must11+=5+a2*4
        must11+=remain22*4
else:#remain33==0
    a2=remain22-a2
    if a2<0:
        a2=-a2#2x2남은갯수
        must11+=36-a2%9*4
        count=count+a2//9+1
        if a2%9==0:
            must11-=36
            count-=1
    else:#22칸에 22넣고 남은경우, 이때 a2는 남은a2갯수가 아니다
        must11+=a2*4
a1=must11-a1
if a1<0:
    a1=-a1#남은11갯수
    count=count+a1//36+1
    if a1%36==0:
        count-=1
print(count)