안경잡이개발자

728x90
반응형

대회 링크: https://codeforces.com/contest/1345

A번 문제: https://codeforces.com/contest/1345/problem/A

 

[ 문제 해설 ]

 

  이 문제는 그림을 그려가면서 다양한 케이스들을 확인해 보면, 문제 풀이 아이디어를 빠르게 떠올릴 수 있다.

 

  행이나 열의 크기가 1이라면, 항상 퍼즐을 풀 수 있다. 그리고 행이나 열의 크기가 둘 다 2, 2일 때에도 항상 퍼즐을 풀 수 있다. 하지만 그 이외의 모든 경우에 대해서는 퍼즐을 풀 수 없다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n, m = map(int, input().split())

    # 행이나 열의 크기가 1이라면 풀 수 있음
    if n == 1 or m == 1:
        print("YES")
    # 행과 열의 크기가 모두 2일 때 풀 수 있음
    elif n == 2 and m == 2:
        print("YES")
    # 이외의 경우에는 모두 풀 수 없음
    else:
        print("NO")

 

B번 문제: https://codeforces.com/contest/1345/problem/B


  이 문제는 N장의 카드를 가지고 있을 때, 최대한 높은 층의 카드 쌓기를 반복적으로 수행하는 문제이다. 그래서 마지막에 몇 개의 카드 피라미드가 존재할 지 출력하면 된다.

 

  아래의 그림에서 볼 수 있듯이,

 

  1층짜리 피라미드: 2장 필요

  2층짜리 피라미드: 7장 필요

  3층짜리 피라미드: 15장 필요

 

 

  그래서, 예를 들어 N = 24라고 해보자.

 

  처음에 15장을 투자해 3층짜리 피라미드를 짓고, 9장이 남는다.

  그리고 7장을 투자해 2층짜리 피라미드를 짓고, 2장이 남는다.

  남은 2장을 투자해 1층짜리 피라미드를 짓고, 0장이 남는다.

 

  그래서 결과적으로 피라미드를 3개 지을 수 있게 된다.

 

[ 문제 해설 ]

 

  이 문제를 해결하기 위한 방법은 간단하다. 문제에서 요구하는 내용을 그대로 구현하면 된다. 이 때 피라미드는 층이 증가할수록 다음과 같이 카드가 필요하다는 특징이 있다.

 

  - 1층 피라미드: 2장

  - 2층 피라미드: 2장 + 5장

  - 3층 피라미드: 2장 + 5장 + 8장

  - 4층 피라미드: 2장 + 5장 + 8장 + 11장

  - 5층 피라미드: 2장 + 5장 + 8장 + 11장 + 14장

 

  즉, 층이 올라갈수록 '추가적으로 필요한 카드의 개수는 3장씩 증가'한다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    result = 0

    # 남아있는 카드가 2장 이상이라면, 피라미드 만들기 수행
    while n >= 2:
        # 초기 상태
        summary = 0
        count = 2
        height = 0

        # 더 높이 쌓을 수 없을 때까지 쌓기
        while n >= summary + count:
           summary += count
           count += 3
           height += 1

        # 피라미드 하나를 완성했으므로, n에서 필요한 카드의 개수만큼 빼주기
        result += 1
        n -= summary

    print(result)

 

C번 문제: https://codeforces.com/contest/1345/problem/C


  이 문제는 비둘지깁의 원리같은 느낌의 문제다. 

728x90
반응형

Comment +0