[백준] 16198번 에너지 모으기

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

16198번: 에너지 모으기

알고리즘 분류: 브루트포스, 백트래킹, 재귀

 

백준 알고리즘 풀면서 항상 느끼는거지만 입력 형식, 출력 형식 맞추는거 너무 힘들다ㅠ

시간이 지나면 익숙해지겠지

 

이번 문제는 브루트 포스, 재귀를 이용해서 해결했다. 브루트포스와 백트래킹 알고리즘에 대해서 스터디를 진행했지만 백트래킹은 구분이 잘 가지 않는다. 언젠간..문제를 풀다보면..이해가 가고 구분이 가겠지..

 

정답 코드 설명

s는 입력받을 문자의 수, n은 입력받을 W들을 저장할 배열이다.

findBiggest(list L): 리스트 L을 인자로 받아서 에너지의 합이 가장 클 때 반환한다. 재귀함수

입력받은 list의 크기가 3일 때는 0,2 인덱스의 값을 곱해서 바로 반환한다.

만약 list 크기가 4 이상이면 모든 경우의 수를 시도해보고 값을 비교해서 가장 큰 값을 반환한다.

근데 결국 이 비교하는 부분에서 모든 경우의 수를 시도한다고 생각이 되서 브루트 포스라고 결론을 내렸다.

그러면 백트래킹은 대체 언제 어떻게 쓰는걸까....아직 잘 모르겠다..

아무튼 모든 경우의 수를 시도하고 가장 큰 값을 반환한다. 

브루트 포스가 가능한 이유는 아마 문제의 조건 때문인 것 같다.

첫째 줄에 에너지 구슬의 개수 N(3 ≤ N ≤ 10)이 주어진다.
둘째 줄에는 에너지 구슬의 무게 W1, W2, ..., WN을 공백으로 구분해 주어진다. (1 ≤ Wi ≤ 1,000)

위의 조건 중 첫번째가 브루트 포스 알고리즘을 가능하게 한다.

구슬의 개수가 10개로 적은 편이고 이정도 연산은 컴퓨터가 무리 없이 할 수 있다.

만약 구슬의 개수가 좀 더 많았으면 브루트 포스로 제 시간에 끝내기에는 무리가 있지 않았을까

정답으로 인정된 코드는 아래와 같다. 

 

s=int(input())
n= [int(x) for x in input().split()]

def findBiggest(L):
  m=0
  if len(L)==3:
    return L[0]*L[2]
  else:
    for i in range(1,len(L)-1):
      temp = L[i-1]*L[i+1]+(findBiggest(L[:i]+L[i+1:]))
      m = max(temp,m)
    return m

print(findBiggest(n))

---

오답코드

항상 알고리즘을 풀면서 더 좋은 방법은 없을까 하며 시간을 투자하는 경우가 많다.

좋은 습관일 수도 있지만 어떻게 보면 욕심을 내려놓지 못하면 문제를 해결하지 못하는 경우가 더 많다는 문제가 있다.

이번 문제도 마찬가지였다. 효율적이고 빠른 방법을 찾고 싶어서 문제 분석에 시간을 투자해서 도출된 가정을 바탕으로 알고리즘을 짜봤는데 계속 실패했다. 아마 내가 놓친 부분이 있었겠지라고 생각하지만 언젠가 다시 풀었을 때 놓친부분을 찾을 수도 있으니 적어보려고 한다.

1. 몇번째 구슬을 선택할지에 대한 문제

조건에 맞지 않는 경우의 수 까지 모두 시도해 볼 필요는 없다고 생각해서 정답인 구슬을 선택하는 것에 초점을 맞췄다.

구슬을 선택하는 방법 3가지를 생각해보았다.

 

1) 가장 큰 수와 이웃한 수 중 작은 수를 선택한다 -> 매번 큰 수를 찾는 것이 더 어렵다는 문제

2) 순서대로 다 해본다 -> 브루트 포스(좋은 방법이 아니라고 생각했으나 이걸로 해결하게 됨)

3) 구슬 하나씩 뺄 때 마다 가장 큰 에너지를 내는 수를 고른다. -> 이걸 선택했다.

 

3번을 선택했을 때 해결해야하는 조건이 하나 더 있다고 생각했다.

-> 만약 같은 크기의 에너지를 낸다면 값이 더 작은 구슬을 뺄 것

 

이렇게가 내가 생각했던 나름 효율적인 알고리즘이었지만 바로 실패실패실패...

눈물이 난다..ㅠ

 

s=int(input())
n= [int(x) for x in input().split()]

def findBiggest(L):
  m=0
  index=0
  if len(L)==3:
    return L[0]*L[2]
  else:
    for i in range(1,len(L)-1):
      if(L[i-1]*L[i+1]>m):
        m=L[i-1]*L[i+1]
        index=i
      elif(L[i-1]*L[i+1]==m and L[i]<L[index]):
        index=i
    del L[index]
    return m+findBiggest(L)

print(findBiggest(n))

findBiggest(list L): 재귀함수

- 1~len(L)-1 중 에너지 크기가 가장 큰 i를 찾는다.

- 만약 에너지 크기가 같으면 에너지 값이 더 작은 수를 뺄 구슬로 선택한다.

- 이전 값과 더하고 다음 list에 대해 재귀함수 호출해서 값을 만들어낸다.

 

예제로는 테스트를 통과했지만 제출은 계속 실패했다...

이유를 꼭 찾고 싶은데 아마 가장 큰 값만 뽑아낸다고 해서 최선의 결과가 나오는 것은 아니라는 결론이 나왔다.

실수가 있다면 찾고 싶은 마음......ㅠ