백준 1111번 파이썬 풀이

홍태리·2022년 2월 1일

백준 브루트포스 알고리즘 알고리즘 파이썬

백준

목록 보기

2/9

문제 원본 링크 : 백준 1111번 문제

두 번째 문제로는 그리디 알고리즘에 대한 문제를 풀어보고 싶었지만, 생각해보니 브루트포스 알고리즘에 관련된 문제를 몇 문제 더 풀어보면서 이해도를 높이는 것도 나쁘지 않을 것 같았다.

그래서 백준 메인페이지에서
문제 > 알고리즘 분류 > 브루트포스 알고리즘 > 옵션:정답비율순, 오름차순
을 검색한 후 적당해보이는 문제를 하나 골랐다.

백준 1111번 문제

첫 시도, 잘못된 코드

#백준 1111번

num = int(input())
nums = list(map(int, input().split()))

#답이 되는 규칙은 항상 (앞 수) * a + b = (뒷 수)
#주어지는 숫자 배열은 모두 절댓값이 100보다 작거나 같으므로
#a는 최소 -100, 최대 100 / b는 최소 -200, 최대 200

def rule(n, a, b):
  return (n * a) + b

def find_rule(n_list):
  answers = set()
  for a in range(-100, 101): #가능한 모든 a의 경우 수
    for b in range(-200, 201): #가능한 모든 b의 경우 수
      test = [n_list[0]]
      for i in range(num):
        if i == 0:
          continue
        else:
          test.append(rule(test[i-1], a, b)) #현재의 (a,b) 규칙을 따르는 리스트 생성
      if test == nums:
        answers.add(nums[-1]*a+b) #생성된 리스트가 주어진 숫자 배열(nums)와 같은 지 비교
  if len(answers) == 1:
    return answers
  elif len(answers) == 0:
    return 'B'
  else:
    return 'A'

def solve():
  if num == 1:
    print('A')
  else:
    blank = find_rule(nums)
    if blank == 'A' or blank == 'B':
      print(blank)
    else:
      for i in blank:
        print(i)

solve()

꽤 논리도 잘 짠 것 같고 해서 자신만만하게 채점을 눌러보았다.

채점 퍼센티지가 올라갈 때마다 설레는 마음으로 결과를 기다렸는데...!

틀렸습니다

그럼 그렇지... ㅎㅎㅎ

이제 공부 이틀 째인데 한 번에 맞추면 그것도 이상하다.

(그래도 한 번에 맞았으면 기분 좋았을 것 같다..)

수정한 코드

#백준 1111번

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

def find_rule(num_list):
  a = int((num_list[2] - num_list[1]) / (num_list[1] - num_list[0]))
  b = num_list[1] - (a * num_list[0])
  return a, b

def same_num(num_list):
  for i in range(len(num_list)):
    if i == 0:
      continue
    if num_list[i-1] == num_list[i]:
      pass
    else:
      return False
  return True

def solve():
  if n == 1:
    print('A')
  elif n == 2:
    if arr[0] == arr[1]:
      print(arr[-1])
    else:
      print('A')
  else:
    if arr[0] == arr[1]:
      if same_num(arr):
        print(arr[-1])
      else:
        print('B')
      return
    sample = [arr[0]]
    a, b = find_rule(arr)
    for i in range(n):
      if i == 0:
        continue
      sample.append(a*arr[i-1]+b)
    if sample == arr:
      print(a*arr[-1]+b)
    else:
      print('B')

solve()