문제 정보
https://www.acmicpc.net/problem/2628
문제
아래 <그림 1>과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다.
<그림 1>
점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 예를 들어, <그림 1>의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 <그림 2>와 같이 여러 개의 종이 조각으로 나뉘게 된다. 이때 가장 큰 종이 조각의 넓이는 30㎠이다.
<그림 2>
입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오.
입력
첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 입력되는 두 숫자 사이에는 빈 칸이 하나씩 있다.
출력
첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다. 단, 넓이의 단위는 출력하지 않는다.
접근방법
총 길이에서 자른 만큼과 자르고 남은 길이를 어떻게 저장할 수 있을까?
전부 다 자른 후 남은 길이는 어떻게 저장할 수 있을까?
자른 길이가 음수가 나오지 않게 하는 방법은 어떤게 있을까?
1차 풀이(오답)
r, c = map(int, input().split()) # r c 길이를 입력
loop = int(input()) #자르는 반복 횟수
rc = [] # r 을 자른 만큼의 길이
cc = [] # c 를 자른 만큼의 길이
for _ in range(loop):
div, num = map(int, input().split())
if div == 0: # 세로길이를 자름
c2 = c - num
cc.append(c2)
c = c - c2
else: # 가로 길이를 자름
r2 = r - num
rc.append(r2)
r = r - r2
else:
cc.append(c)
rc.append(r)
dap = max(rc) * max(cc)
print(dap)
예제로 주어진 테스트 케이스에서는 답이 나왔지만
작은숫자가 먼저 들어왔을 경우에 대한 처리를 해주지 못했다.
0 3 0 2
1 4 => 1 4
0 2 0 3
왼쪽의 예제를 오른쪽 처럼 변경 하면
cc 리스트에 음수가 저장되고 출력값도 달라지게 된다.
2차 풀이(통과)
r, c = map(int, input().split()) # r c 길이를 입력
loop = int(input()) #자르는 반복 횟수
divL = []
rc = [] # r 을 자른 만큼의 길이
cc = [] # c 를 자른 만큼의 길이
for _ in range(loop):
div, num = map(int, input().split())
divL.append((div, num))
sortedDiv = sorted(divL, reverse=True)
for i in range(len(sortedDiv)):
if sortedDiv[i][0] == 0:
c2 = c - sortedDiv[i][1]
cc.append(c2)
c = c - c2
else:
r2 = r - sortedDiv[i][1]
rc.append(r2)
r = r - r2
else:
cc.append(c)
rc.append(r)
print(max(rc) * max(cc))
divL
이라는 자르고자 하는 정보를 담는 리스트를 새로 만들어 주었다.
for 문을 순회하면서 정보를 담고
sorted 를 통해서 내림차순 정렬 해 주었다.
입력된 값을 정렬해 주었기 때문에 작은 숫자부터 종이를 자르는 경우는 사라졌고
rc, cc 리스트에는 음수가 들어가지 않게 되었다.
느낀점
1. 주어진 예제 대로만 처리하려 해서 문제를 너무 간단하게 생각했던 것 같다.
2. 현재 알고리즘 주간인 SSAFY 에서는 내장 메소드를 금지하고 있는데 백준이라 그냥 사용했다.
정렬 자체는 그렇게 어렵지 않으니 직접 해도 됐겠지만 코드가 길어졌을 것같다.
3. 아직 sorted
와 sort
의 차이를 정확하게 알고있지 못하는 것 같다. 계속해서 디버깅 하면서 문제를 해결했다.
4. for 문을 끝마친 뒤 마지막 값을 어떻게 넣을지 고민했었는데 for else
를 통해서 잘 해결한 것 같아 뿌듯하다
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 15649 N과 M (1) (파이썬) (0) | 2022.09.05 |
---|---|
백준 2667 단지번호붙이기(파이썬) (0) | 2022.09.04 |
백준 7576 토마토(파이썬) (0) | 2022.09.02 |
백준 2477 참외밭(파이썬) (0) | 2022.08.25 |
SWEA 4875. [파이썬 S/W 문제해결 기본] 5일차 - 미로(파이썬) (0) | 2022.08.24 |