[백준 완전탐색] 고층 건물

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

 

문제설명

문제를 딱 보자마자 완전탐색이라고 생각했다. 건물들을 하나씩 비교하며 카운팅을 하 쉽게 풀 수 있을 거라고 생각했다.

빌딩의 수도 적으니 3중 반복문도 시간초과가 안날 것이라고 생각했다.

해결과정

첫풀이

n = int(input())
arr = list(map(int, input().split()))

for i in range(n):
  cnt = 0
  for j in range(n):

    if i == j:
      continue

    target = abs(arr[j] - arr[i]) / abs(j - i)
    start = min(i, j)
    end = max(i, j)

    flag = True

    if end - start == 1:
      if arr[i] >= arr[j]:
        cnt += 1
        continue
      else:
        continue

    for k in range(start + 1, end):
      if arr[i] < arr[j] or (arr[i]>=arr[j] and arr[k] >= arr[i]):
        flag = False
        continue
        
      if abs(arr[j] - arr[k]) / abs(j - k) > target:
        flag = False
        continue
    if flag:
      cnt += 1

    if i==2 and j==1:
      print(flag)

  print(cnt, end=" ")

# https://www.acmicpc.net/problem/1027

 

몇 개의 테스트 코드는 통과하는 걸로 보이지만 첫 번째 테스트 케이스에서 값이 맞지 않았다.

 

 

최대값이 7이 나와야 하는데 내가 짠 코드를 돌리면 4가 최대였다. 결과값을 확인해보니 로직은 어느 정도 맞는 것 같다. 한 번 코드를 적고 결과값을 확인하니 아직 내가 첫 테스트 케이스의 답이 왜 7이 나오는지 제대로 이해 못했었다. 하나하나 건물들을 그려보니 내가 놓치고 있는게 있었다. 기울기를 비교하는 로직은 (i,j) 사이에 있는 k가 arr[i]>arr[k]>arr[j], arr[j]<arr[k]<arr[i] 의 관계에 있을때이다.

 

한 번 이걸 고려하여 다시 작성해보자

 

n = int(input())
arr = list(map(int, input().split()))

for i in range(n):
  cnt = 0
  for j in range(n):

    if i == j:
      continue

    target = abs(arr[j] - arr[i]) / abs(j - i)
    start = min(i, j)
    end = max(i, j)

    flag = True

    if end - start == 1:
      if arr[i] >= arr[j]:
        cnt += 1
        continue
      else:
        continue

    for k in range(start + 1, end):
      if arr[i] < arr[j] or (arr[i] >= arr[j] and arr[k] >= arr[i]):
        flag = False
        continue

      if arr[k] >= arr[j] or arr[k] >= arr[i]:
        continue

      if abs(arr[j] - arr[k]) / abs(j - k) > target:
        flag = False
        continue

    if flag:
      cnt += 1

  print(cnt, end=" ")

# https://www.acmicpc.net/problem/1027

 

위와 같이 7이 잘 나오는 걸 확인했다. 

 

다만 위 코드로는 5번 테스트 케이스를 통과하지 못했다.

 

위 테케의 출력이 6인 이유는 아마 첫번째 건물에서 보이는 건물일 것이다.

 

N = int(input())

building = list(map(int, input().split()))
answer = 0

for i in range(N):
  temp = N - 1
  for j in range(i+1, N):
    for k in range(i+1, j):
      if building[k] - building[i] >= (((building[j] - building[i])/(j-i)) * (k-i)):
        temp -= 1
        break

  for j in range(0,i):
    for k in range(j+1, i):
      if building[k] - building[j] >= (((building[i] - building[j])/(i-j)) * (k-j)):
        temp -= 1
        break

  answer = max(answer, temp)

print(answer)

 

최종적으로 코드를 수정해보았다