20210201_코테공부

# 1932 정수 삼각형 (실버1)

• 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
• Point. 모든 경로를 따지면 2^50 -> 이번생에 못푼다
• DP문제 (다음 상태를 저장하고 사용함)
  1. 상태를 정의한다 
  2. 점화식을 찾는다(구한다) 
  3. 시간복잡도를 계산한다
  4. 코딩한다(재귀 or 반복문 사용)

N = int(input())
# DP[i][j] : i,j 도착했을 때 최대값
# DP[i][j] = max(DP[i-1], DP[i-1][j]) + A[i][j]
A = [[0 for _ in range(N+1)] for i in range(N+1)]
DP = [[0 for _ in range(N+1)] for i in range(N+1)]

for i in range(1, N+1):
    tmp = list(map(int, input().split()))
    for j in range(1, i+1):
        A[i][j] = tmp[j-1]

for i in range(1, N+1):
    for j in range(1, i+1):
        DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + A[i][j]

print(max(DP[-1]))

(오른쪽 : 예시 입력값 / 왼쪽 : DP 출력값 -> DP의 마지막 줄에 max값이 최대값이다)

 

단계별풀기 - 브루트 포스

# 7568 덩치 (실버5)

• 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다.
• 여러분은 입력에 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백문자로 분리되어야 한다.
• point. 정렬 ㄴㄴ, 그냥 자기보다 크고 무거운(둘 다 큰) 사람이 몇 명인지 쟤서 자기 등수만 정하면 된다.

tc = int(input())
student_list = []

for _ in range(tc):
    x, y = map(int, input().split())
    student_list.append((x, y))

for i in student_list:
    rank = 1
    for j in student_list:
        if i[0] < j[0] and i[1] < j[1]:
                rank += 1
    print(rank, end = " ")