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

풀이

• 단순 수학 문제
• 문제에 주어진 대로 따라가면 쉬운 문제
• 계속 틀렸다고 나옴
• 다시 풀어봐야 함

​

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

풀이

• dp

• 가장 긴 증가하는 수열과 같은 문제

• d[i] : i 를 마지막으로 하는 가장 긴 증가하는 수열

• d[i]

    0 번째 ~ i-1 번째까지 조사.
  

  ​ k번째에서 i번째 수보다 작고, 더 긴 증가하는 부분수열이 된다면
  ​ d[i] = d[k] + 1

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

풀이

• dp

• 쉬운 문제

• d[i]

    d[i-2] + d[i-3] + d[i-4] + d[i-1]
  

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

풀이

• dp

• 잘못된 접근 : 현재 위치에서, 갈 수 있는 곳만 생각했음

• 올바른 접근 : 현재 위치를, 올 수 있는 곳을 생각해야함

  1 2 3 4

  1 2 3 4 4를 올 수 있는 곳은 1, 2, 3

• d[i][j] : i,j 위치에서의 사탕 개수 최대값

  Max(
  ​ [i-1][j-1]에서의 사탕개수 최대값,
  ​ [i][j-1]에서의 사탕개수 최대값,
  ​ [i-1][j]에서의 사탕개수 최대값) + i,j에서의 사탕개수

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

풀이

• dp

• 그림으로 쉽게 풀림

• 점화식
  ​

    s[i][j] = a[i][j] + s[i-1][j] +s[i][j-1] - s[i-1][j-1] 
  

• ( i,j,x,y 의 구간합 )

    s[x][y] -s[ i-1][y]  - s[x][j-1] + s[i-1][j-1 ]
  

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

풀이

• dp

• d[i][color]

    i 번째 집을 color 로 칠했을 때, 1 번째~ i 번째 까지 든 최소 비용
  

• d[i+1][0] = i번째 집을 1번으로 칠했을 때 든 최소 비용과, 2번으로 칠했을 때 든 최소비용 중 작은 값

• d[i+1][1] = i번째 집을 0번으로 칠했을 때 든 최소 비용과, 2번으로 칠했을 때 든 최소비용 중 작은 값

• d[i+1][2] = i번째 집을 0번으로 칠했을 때 든 최소 비용과, 1번으로 칠했을 때 든 최소비용 중 작은 값

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

풀이

• 매우 쉬운 문제
• string 으로 붙이면 됨
• StringTokenizer
• hasMoreTokens
• 출력할 때 int로 하면 런타임에러
• 그래서 long long 으로 했음

결과

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

풀이

• 상하좌우 조사
• 현재 위치를 상하좌우 조사한 위치에서 올 수 있는지 확인
• 재귀
• 계속 d 배열이 채워지질 않는다..

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

풀이

• bj_1167 과 동일한 문제
• 1을 루트로 지정하고 가장 먼 위치에 있는 정점 찾고
• 그 정점에서 모든 정점들 사이의 거리 찾아서
• 가장 큰게 답

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

풀이

• bfs로 탐색
• 루트에서 모든 정점까리 거리 구함
• 가장 먼 거리 정점 : A
• A는 이제 루트
• 모든 정점까지 거리 구함
• 가장 먼 거리가 지름