수학과의 개발자 도전기

-문제:https://www.acmicpc.net/problem/1932

이전에 풀었던 과정은 여기에 있다

-정답풀이:

이전에 풀었던 문제라서 풀이과정이 비교적 쉽게 생각이 났다. 

과정

열이 0이거나 행과 같은 경우는 해당 숫자에 바로 위 숫자를 더하면 된다(여기서 열==0 인 경우와 열==행인 경우 다르게 설정해야 한다)

이외의 경우는 왼쪽, 오른쪽 위의 값 중 최댓값을 더해주면 된다 

다만 indexError가 계속 발생했는데, 이는 처음에 data를 data=[[] for _ in range(n)]으로 초기화 했었다. 

여기서 list를 삽입하면 3중 리스트가 되어서 계속 났던 것이다

그래서 data=[]라고 초기화한 후, 분기문에서 이전 값들을 data의 값이 아닌 dp의 값으로 대체했더니 정답이 떴다  

n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
dp=[[0]*n for _ in range(n)]
dp[0][0]=data[0][0]
for i in range(1,n):
    for j in range(0,i+1):
        if j==0:
            dp[i][j]= (dp[i-1][j]+data[i][j])
        elif i==j:
            dp[i][j]=dp[i-1][j-1]+data[i][j]
        else:
            dp[i][j]= data[i][j]+max(dp[i-1][j-1],dp[i-1][j])
        
            
print(max(dp[-1]))

-문제:https://www.acmicpc.net/problem/14002

이전에 풀었던 LCS2와 같은 유형이라 참고해서 풀었다. 풀이없이 푼 문제 

-정답풀이: 

• 윗부분은 가장 긴 증가 부분수열으로 코드 작성하면되고
• 수열 숫자 출력하는 부분은 수열 마지막 숫자부터 시작해서 값을 하나씩 줄이면서 나가면된다
• 숫자 출력시 숫자간 띄어쓰기가 필요하므로 14번 라인 중간에 '  '(공백)을 추가한다 
• 14번처럼 작성하면 숫자가 순서대로 출력된다(입력되는 순서를 입력해서 그런가?)
• 밑에 틀린 풀이 때문에 한동안 시간을 잡아먹었다 

-틀린풀이: 

• 13번, 14번 라인으로 인해서 오류가 났다
• 13번 때문에 10 20 30 50 으로 출력될 게 10 30 50 으로 출력돼서 틀렸음 

-문제: https://www.acmicpc.net/problem/1965

가장 긴 증가하는 부분수열 문제

-정답풀이:

n=int(input())
data=list(map(int,input().split()))
dp=[0]*n

for i in range(n):
    for j in range(i+1):
        if data[i]>data[j] and dp[i]<dp[j]:
            dp[i]=dp[j]
    dp[i]+=1
print(max(dp))

-문제: https://www.acmicpc.net/problem/17070

깊이우선 탐색인 것 같은데 이전에 풀었던 문제는 동,서,남,북 네 방향이었는데 이거는 대각선 포함 방향 3개라서 또 새로운 문제였다 

-정답풀이1: 

• pypy3으로 돌려야지 시간초과가 안 뜬다 
• 방향이 세개인 걸 shape으로 나누어서 진행하면 된다 
• 파이프를 옮기다 보면 n-1 컬럼에 있을 때 예외상황을 어떻게 처리해야하는지 잘 몰랐는데 10,14,18번 줄처럼 if문 처리하면 된다 
• 진행할 때 주변에 벽(숫자 1)이 있는지 없는지 확인할 방법은 11,15,19번 줄을 참고하면된다 

-정답풀이2:

• 따로 0행렬을 만들어서 거기에 경우의수 누적하려고 했는데 방향이 3개라서 경우의 수를 나누는게 어려웠다.
• 그런데 이제 같은 크기의 행렬을 3개 만들어서 각각 움직이는 경우의 수 대입한 후에 행렬 오른쪽 끝 값을 모두 더해서 출력하면 답이다.