728x90
난이도 : 골드4
풀이일 : 04307
https://www.acmicpc.net/problem/1027
링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐
중간 과정
처음에는 이렇게 건물 높이를 그림으로 그려놓고 어떻게 접근해야 할 지 생각했다.
실제 코드에서는 저런 식으로 배열을 만들 게 아니니까 메모리 같은 것들은 고려하지 않았고,
건물의 최대 개수도 50개여서 시간도 고려하지 않았다.
# 1. 모든 건물에 대해 좌, 우 방향 탐색
# 2. 볼 수 있는 건물의 개수 세기
# 발견한 옆 건물 높이 기록 buildings[i] > 건물 => h = 0
# 1. 좌측탐색
# 1. h == 0 and buildings[j] < buildings[i]
# 기울기 : (buildings[i]-buildings[j]) / (i-j) 기록
# 기록된 숫자보다 기울기가 작으면 temp += 1, 기울기 재할당
# 2. h == 0 and buildings[j] > buildings[i]
# temp += 1, h = 1
# 기울기 : (buildings[i]-buildings[j]) / (i-j) 기록
# 3. h == 1 and buildings[j] > buildings[i]
# 기록된 숫자보다 기울기가 작으면 temp += 1, 기울기 재할당
# 4. h == 1 and buildings[j] < buildings[i]
# 그냥 넘어가기
# 3. maxi 보다 크다면 재할당
# 4. 최종 maxi 값 출력
import sys
N = int(sys.stdin.readline().strip())
buildings = list(map(int, sys.stdin.readline().split()))
maxi = 0
for i in range(N):
temp = 0
h, r = 0, 1000000001
for j in range(i-1, -1, -1):
if h:
if (buildings[i] - buildings[j]) / (i - j) < r:
r = (buildings[i] - buildings[j]) / (i - j)
temp += 1
print(f'i={i}, j={j}, r={r}')
else:
if buildings[j] < buildings[i] and (buildings[i] - buildings[j]) / (i - j) < r:
r = (buildings[i] - buildings[j]) / (i - j)
temp += 1
print(f'i={i}, j={j}, r={r}')
elif buildings[j] > buildings[i]:
r = (buildings[i] - buildings[j]) / (i - j)
temp += 1
h = 1
print(f'i={i}, j={j}, r={r}')
elif buildings[j] == buildings[i]:
r = 0
temp += 1
h = 1
print(f'i={i}, j={j}, r={r}')
h = r = 0
for j in range(i + 1, N):
if h:
if (buildings[j] - buildings[i]) / (j - i) > r:
r = (buildings[j] - buildings[i]) / (j - i)
temp += 1
print(f'i={i}, j={j}, r={r}')
else:
if buildings[j] < buildings[i] and (buildings[i] - buildings[j]) / (j - i) > r:
r = (buildings[j] - buildings[i]) / (j - i)
temp += 1
print(f'i={i}, j={j}, r={r}')
elif buildings[j] > buildings[i]:
r = (buildings[j] - buildings[i]) / (j - i)
temp += 1
h = 1
print(f'i={i}, j={j}, r={r}')
elif buildings[j] == buildings[i]:
r = 0
temp += 1
h = 1
print(f'i={i}, j={j}, r={r}')
print(f'i={i}, temp={temp}')
if temp > maxi:
maxi = temp
print(maxi)
며칠 동안 도전하는 족족 실패해서 오늘은 꼭 맞추겠다고 생각부터 하고 코드를 짰다.
완성 됐다 생각하고 확인하는데 마지막 예제 출력이 틀리게 나와서 print문을 찍어보다가 중단
다시 생각해보니까 어차피 기울기는 buildings[j] 값이 buildings[i] 보다 크건 작건 상관 없이 한 조건인데? 싶어져서 수정 시작
풀이 코드
# 1. 모든 건물에 대해 좌, 우 방향 탐색
# 2. 볼 수 있는 건물의 개수 세기
# 1. 좌측탐색 -> 기울기 -
# 기울기 : (buildings[i] - buildings[j]) / (i - j)
# 2. 우측탐색 -> 기울기 +
# 기울기 : (buildings[j] - buildings[i]) / (j - i)
# 3. maxi 보다 크다면 재할당
# 4. 최종 maxi 값 출력
import sys
N = int(sys.stdin.readline().strip())
buildings = list(map(int, sys.stdin.readline().split()))
maxi = 0
for i in range(N):
temp = 0
r = 1000000001
for j in range(i-1, -1, -1): # 좌측탐색
if (buildings[i] - buildings[j]) / (i - j) < r:
r = (buildings[i] - buildings[j]) / (i - j)
temp += 1
r = -1000000001
for j in range(i + 1, N): # 우측탐색
if (buildings[j] - buildings[i]) / (j - i) > r:
r = (buildings[i] - buildings[j]) / (i - j)
temp += 1
if temp > maxi:
maxi = temp
print(maxi)
정신차리고 간결하게 정리한 정답 코드
코드 구성
- 모든 건물에 대해 좌, 우 방향 탐색
- 기준 건물의 좌측 탐색 시, 기울기가 작으면 추가
- 우측 탐색은 기울기가 크면 추가
- 한 기준 건물에서 보이는 건물 수와 최댓값 비교 후 재할당
느낀점
최근 며칠 시간을 많이 쏟고도 실패해서 티스토리를 못 올리거나 세이브 된 것들을 올리며 오늘은 꼭 풀겠다는 생각에 괜히 엉뚱한 짓만 함
정신차리고 내가 잘 풀 수 있는 문제는 정확하게, 빠르게 풀 수 있도록 연습하자
'알고리즘 > 🥇 골드' 카테고리의 다른 글
백준 2252 줄세우기 파이썬 풀이 (0) | 2023.05.04 |
---|---|
백준 1005 ACM Craft 파이썬 풀이 (0) | 2023.05.03 |
백준 16236 아기상어 파이썬 풀이 (0) | 2023.04.27 |
백준 17298 오큰수 파이썬 풀이 (0) | 2023.04.25 |
백준 14719 빗물 파이썬 풀이 (0) | 2023.04.24 |