백준 11053번

김가람·2023년 3월 25일
0

1. 문제

11053

2. 풀이

  • 처음은 iteration 별로 숫자가 증가하는 경우의 수만 count하는 식으로 쉽게 접근 했다.
N = int(input())
num = list(map(int, input().split()))

cnt = 1
max_ = num[0]
for i in range(1, N):
    if num[i] > max_: # i번째 숫자를 i-1까지의 숫자 중 최댓값과 비교
        cnt += 1 # 값이 증가하면 +1
        max_ = num[i] # 최댓값 갱신
        
print(cnt)
  • 예시 문제에 나오는 10 20 10 30 20 50 의 경우 정답 4가 아무런 문제 없이 출력된다.

  • 그러나.... 1 100 101 2 3 4 5 와 같이 중간에 매우 큰 숫자가 나오면 그 다음 숫자에 대해서는 전혀 고려되지 않는 반례가 있어 틀렸다.

  • 이 문제는 i번째 대소를 고려할 때, 0번째 부터 i-1번째까지 모든 숫자를 고려해야 한다. 즉, 이중 반복문으로 접근해야 한다.

index0123456
number11001012345
dp1232345
  • 예를 들어 위 표에서 index 3의 숫자 2의 대소 비교는 index 0 ~ 2까지 1, 100, 101과 각각 비교 되어야 한다.

  • 그리고 각 index의 숫자와 비교하여 큰 경우에만 counting 하여 dp에 그 값을 저장한다. 여기서는 index 0보다 크기 때문에 index0의 dp 인 1에 1을 더한 2를 저장한다.

  • 이렇게 하면 중간에 매우 큰 숫자인 100, 101을 피하여 수열을 이어 나갈 수 있다.

  • 코드로 구현하면 아래와 같다.

N = int(input())
number = list(map(int, input().split())

dp = [1 for _ in range(N)]

for i in range(N):
	for j in range(i): # i번째 숫자와 대/소를 비교
    	if number[i] > number[j]:
        	# j번째 dp에 1을 더한 값과 j-1번째 dp에 1을 더한 값을 비교하여 더 큰 값을 저장
        	dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
  • 처음 문제를 접했을 때 완전히 잘못 생각하여 접근 했었다. 공부를 할수록 점점 더 한계를 느껴가는데... 이 분야에서 과연 일정 수준의 성취를 얻을 수 있을지 고민된다. 그래도 매일 꾸준히 하는 것이 내가 할 수 있는 최선인 것 같다. 오늘도 하고, 내일도 하고 내일 모레도 할 것이다. 그러다 보면 실력이 일취월장 하는 순간이 오지 않을까?
profile
부캐:데이터 사이언티스트가 되고 싶은 반도체 공장 노예

0개의 댓글