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

풀이

1. GCD 구하는 함수를 만든다

2. 모든 쌍을 반복문 통해서 확인

3. 더해서 출력

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

풀이

1. 최대공약수를 구한다
2. 최소 공배수 = 두 수의 곱 / 최대공약수

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

풀이

1. 유클리드 호제법 이용

2. r = a%b

3. gcd(a , b) == gcd (b, r)

4. r==0 이면
   이때 b가 gcd

​

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

풀이

1. 그냥 풀면 됨

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

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

1

%100007

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

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

풀이

1. 가장 긴 증가하는 부분 수열과 동일

2. 다른 점

   • 증가하는 수열이 아닌 감소하는 수열
     검색할 때의 조건이 자신보다 높은값만 찾으면 됨
   • a[j] > a[i]

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. 햇갈리니까 표를 그리자!!

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보다 작기 때문에 그대로

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

풀이 1) 이차원 배열

1. d[i][j]

   • 1~i 번째 포도주까지 마셨을 때, 마실 수 있는 포도주의 최대 양
     
     i번째 포두주 잔은 j 번 연속 마신 포도주 잔임

2. a[i]

   • (i : 1~n)
   • i 번째 포도주의 양

3. 결과

   • d[n][0] = max( d[n-1][0] , d[n-1][1], d[n-1][2] )
   • d[n][1] = d[n-1][0] + a[n]
   • d[n][2] = d[n-1][1] + a[n]

풀이 2) 일차원 배열

1. d[i]

   • 1~i 번째 포도주까지 마셨을 때, 마실 수 있는 포도주의 최대 양

2. a[i]

   • (i : 1~n)
   • i 번째 포도주의 양

3. 결과

   • 0번 연속 : d[i] = d[i-1]
   • 1번 연속 : d[i] = d[i-2] + a[i]
   • 2번 연속 : d[i] = d[i-3] + a[i-1] + a[i]

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

풀이

1. s : n열의 상태

   • [0] [1] [2]
   • X O X
   • X X O

2. d[n][s]

   • 2 x n 에서 얻을 수 있는 최대 점수. n열에서 뜯은 스티커는 s

3. a[i][j]

   • i열 j행에 들어있는 스티커의 점수

4. 결과

   • d[n][0] = max( d[n-1][0] , d[n-1][1] , d[n-1][2] )
   • d[n][1] = max( d[n-1][0] , d[n-1][2] ) + a[n][1]
   • d[n][2] = max( d[n-1][0] , d[n-1][1] ) + a[n][2]

5. 정답

   • max( d[n][0], d[n][1], d[n][2] )

==> 어렵다. 다시 풀어야함

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

풀이 1)

1. d[n][l]
   • 자리가 n & 끝자리가 l 인 이친수의 개수
2. d[n][0]
   • d[n-1][0] + d[n-1][1]
3. d[n][1]
   • d[n-1][0]
4. ans
   • d[n][0]+d[n][1]

=> 근데 왜 답은 틀렸다고 나올까..?

풀이 2)

1. d[n]
   • n 자리 이친수의 개수
   • d[n-1] + d[n-2]

=> 이 방법도 틀리게 나옴