[백준] 3602번: iChess 파이썬 풀이

사용한 기술 스택들:  

 

3602번: iChess (acmicpc.net)

3602번: iChess

 

3602번: iChess

코드

# O(1)

import sys

input = sys.stdin.readline
n,m=sorted(map(int,input().split()))
if m==0:
    print("Impossible")
else:
    if n==m:
        print(int((n*2)**0.5))
    else:
        print(int((n*2+1)**0.5))

# bruteforce

# import sys

# input = sys.stdin.readline
# n,m=sorted(map(int,input().split()))
# if m==0:
#     print("Impossible")
# else:
#     ans=0
#     for i in range(1,143):
#         total_tiles=i**2
#         if i%2==0:
#             w_tiles = total_tiles//2
#             b_tiles = total_tiles//2
#         else:
#             w_tiles = total_tiles//2
#             b_tiles = total_tiles//2+1
#         if w_tiles <= n and b_tiles <= m:
#             ans=i
#         else:
#             break
#     print(ans)

설명

문제 설명을 잠깐 하자면 검정 타일 n개, 하얀색 타일 m개가 있는데 이걸 체스판 형식의 정사각형으로 배치해야 한다. 이때 만들 수 있는 정사각형 체스판 한 변의 최대 길이를 출력해주면 되는 문제이다. 사실 n랑 m이가 10000을 넘지 않아서 bruteforce로 풀어도 되긴 하지만 o(1)로 풀 수 있는 알고리즘도 들고 왔다.

 

체스판은 8의 길이를 가진 32개의 하얀색 타일과 32개 검정색 타일이 있는 정사각형이다

브루트 포스

import sys

input = sys.stdin.readline
n,m=sorted(map(int,input().split()))
if m==0:
    print("Impossible")
else:
    ans=0
    for i in range(1,142):
        total_tiles=i**2
        if i%2==0:
            w_tiles = total_tiles//2
            b_tiles = total_tiles//2
        else:
            w_tiles = total_tiles//2
            b_tiles = total_tiles//2+1
        if w_tiles <= n and b_tiles <= m:
            ans=i
        else:
            break
    print(ans)

일단 여기 코드를 보면 sorted 해서 n을 무작정 작게 만들어 준다. Impossible이 나오는 상황은 n과 m이 0일 때이기 때문에 더 큰 수인 m만 확인해주면 된다.

 

이제 그다음 코드를 보면, for loop으로 1부터 141까지 돌아주는 걸 볼 수 있다. 여기서 141이라는 숫자가 왜 나오냐면 n과 m의 제한이 각각 10000이기 때문에 √20000 ≈ 141.x 하면 최대로 141의 길이를 가진 정사각형을 만들 수 있다. 1부터 시작해서 이 길이를 가진 정사각형을 만들 수 있는지 확인해준다. 여기서 i%2==0으로 홀수 길이와 짝수 길이를 나누어서 생각해주는 이유는 밑에 사진을 보면 알 수 있는데 변의 길이가 홀수일 때에는 타일이 하나가 더 많고 짝수일 때는 똑같다(그냥 편의상 n을 하얀색 타일, m을 검은색 타일로 하겠다).

 

짝수 길이와 홀수 길이의 타일간의 차이가 다르다

•  홀수일 때는
  • 전체 타일//2(정수 나눗셈): 적은 타일
  • 전체 타일//2 + 1: 많은 타일
• 짝수일 때는
  • 전체 타일//2: 많은 타일, 적은 타일

이제 이걸 가능할 때마다 ans에 저장해서 불가능할 때 break 해서 최대 길이를 출력해주면 된다.

 

O(1) 풀이

import sys

input = sys.stdin.readline
n,m=sorted(map(int,input().split()))
if m==0:
    print("Impossible")
else:
    if n==m:
        print(int((n*2)**0.5))
    else:
        print(int((n*2+1)**0.5))

여기서는 최대 141번만큼 루프를 돌 필요가 없다. 생각해보면 최대길이 x는 √(전체 타일)이라는 걸 알 수 있다.

n과 m이 같지 않으면 최대길이=√(2n+1)이다(m> n이므로 n+m>=2n+1이 성립한다). (아까 그림에서 짝수든 홀수든 무조건 2n+1이면 성립이다)

n과 m이 같다면 홀수 길이 타일에서 걸리기 때문에(반례: 4 4 -> 틀린 출력: 3 답:2) 1을 더해주지 않고 √(2n)이다(m=n이므로 n+m=2n이 성립한다)

 

 

소스코드:

baekjoonProblems/iChess.py at main · LimePencil/baekjoonProblems (github.com)

GitHub - LimePencil/baekjoonProblems: 백준 코딩문제 자바&파이썬 해답