1430:나머지

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

풀이

  1. 그냥 풀면 됨

  2. 이 문제는 풀이가 의미 있는 것이 아니라,
    문제 자체가 의미 있음.
    문제 자체가 알고리즘 풀 때 쓰임.

  3. 다이나믹 문제 풀다가
    int , long long 범위를 넘기 때문에 정답을

1
%100007

이렇게 구하는 문제가 있음.
이것은,
전체 정답을 구하고 나머지 출력하는것이 아님.
중간에 정수 범위를 넘어가기 때문에
중간 중간 나머지 연산 처리 해야함.

Read more

11055:가장 큰 증가 부분 수열

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

틀린 풀이

  1. d[i]

    • a[1] ~ a[i] 중
    • a[i]를 포함하며,
    • 수열의 합
  2. i번째를 기준으로 i-1번째 ~ 1번째로 하나 하나 검색

  3. i번째보다 작으면 d[i]에 더함

맞는 풀이

  1. 앞 문제와 동일하다

  2. 앞 문제의 조건

    • i < j => a[i] < a[j]
    • max(d[j]) + 1 => 여기서 1은 길이
  3. 1을 점수로 바꿔주면 됨

  4. 햇갈리니까 표를 그리자!!

Read more

11053:가장 긴 증가하는 부분 수열

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

틀린 풀이

  1. d[n]

    • 첫번째 ~ n번째 값 중,
    • 가장 큰 수
  2. 10 20 10 30 20 50

    • d[0] = 0
    • d[1] = 10
    • d[2] = 20
    • d[3] = 20
    • d[4] = 30
    • d[5] = 30
    • d[6] = 50
  3. d 배열의 값이 바뀔 때를 count

  4. count 값이 답.

맞는 풀이

LIS 문제. 유명한 문제.

  • d[i]

    • a[1] … a[i] 가 있을 때,
    • a[i]를 마지막으로 하는
    • 가장 긴 증가하는 부분 수열의 길이.
    • d[i]는 a[i] 가 반드시 포함
  • ~ a[j] … a[i]

    • ~ a[j]길이 : d[j] —-> d[j] + 1
  • d[i]

    • max( d[j] ) + 1
  • a[j] 와 a[i]의 관계

    • a[j] < a[i]
1
2
3
4
5
6
7
8
9
  i			1     2     3     4     5     6 
a[i] 10 20 10 30 20 50
d[i] 1 2 1 3 2 4

d[4]를 예를들어,
d[4]는 처음에 1. 왜냐하면 자기 자신하나만 있으면 길이기 1이기 때문에.
a[3]을 봤더니, a[4]보다 작아. 증가하는 수열이기때문에 올 수 있어. 그럼, d[3] +1 = 2. 1보다 크기 때문에. d[4]=2
a[2]을 봤더니, a[4]보다 작아. 증가하는 수열이기때문에 올 수 있어. 그럼, d[2] +1 = 3. 2보다 크기 때문에 d[4] =3
a[1]을 봤더니, a[4]보다 작아. 증가하는 수열이기때문에 올 수 있어. 그럼, d[1] +1 = 1. 3보다 작기 때문에 그대로
Read more