1149번: RGB거리 (acmicpc.net)

#RGB거리: 빨/초/파 중 하나의 색으로 칠해야 한다. 이웃한 집들과는 색이 달라야 한다. 칠하는 최소 비용 구하기.

n = int(input())

graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

빨, 초, 파로 각각의 집을 칠하는 가격 순서대로 입력받아서 그래프로 나타내기

dp = []
for _ in range(n):
    dp.append([0, 0, 0])

dp[0][0] = graph[0][0]
dp[0][1] = graph[0][1]
dp[0][2] = graph[0][2]

for i in range(1, n):
    
    dp[i][0] = min(dp[i-1][1], dp[i-1][2])+graph[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2])+graph[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1])+graph[i][2]
    
    '''
    if dp[i-1][0]+graph[i][1] <= dp[i-1][2]+graph[i][1]:
        dp[i][1]= dp[i-1][0]+graph[i][1]
    else: dp[i][1] = dp[i-1][2]+graph[i][1]
    ↑ 이런 형식에서 간단하게 수정함.
    
    '''
    
print(min(dp[n-1]))

Row, Col = 5, 5
goldMaze = [[1, 4, 4, 2, 2], [1, 3, 3, 0, 5], [1, 2, 4, 3, 0], [3, 3, 0, 4, 2], [1, 3, 4, 5, 3]]

def growRich() :
    memo = [[0 for _ in range(Col)] for _ in range(Row)]
    memo[0][0] = goldMaze[0][0]
    
    rowSum = memo[0][0]
    for i in range(1, Row):
        rowSum += goldMaze[0][i]
        memo[0][i] = rowSum

        
    colSum = memo[0][0]
    for i in range(1, Col):
        colSum += goldMaze[i][0]
        memo[i][0] = colSum
  
        
    for row in range(1, Row):
        for col in range(1, Col):
            if (memo[row][col-1]>memo[row-1][col]):
                memo[row][col] = memo[row][col-1]+goldMaze[row][col]

            else: 
                memo[row][col] = memo[row-1][col]+goldMaze[row][col]

                
    return memo[Row-1][Col-1]

print(growRich())



#최소 압정 미로

Row, Col = 5, 5
goldMaze = [[1, 4, 4, 2, 2], [1, 3, 3, 0, 5], [1, 2, 4, 3, 0], [3, 3, 0, 4, 2], [1, 3, 4, 5, 3]]

def growRich() :
    memo = [[0 for _ in range(Col)] for _ in range(Row)]
    memo[0][0] = goldMaze[0][0]
    
    rowSum = memo[0][0]
    for i in range(1, Row):
        rowSum += goldMaze[0][i]
        memo[0][i] = rowSum

        
    colSum = memo[0][0]
    for i in range(1, Col):
        colSum += goldMaze[i][0]
        memo[i][0] = colSum
  
        
    for row in range(1, Row):
        for col in range(1, Col):
            if (memo[row][col-1]<memo[row-1][col]):
                memo[row][col] = memo[row][col-1]+goldMaze[row][col]

            else: 
                memo[row][col] = memo[row-1][col]+goldMaze[row][col]

                
    return memo[Row-1][Col-1]

print(growRich())




#황금미로에서 길 표시하면서 가기

Row, Col = 5, 5
goldMaze = [[1, 4, 4, 2, 2], [1, 3, 3, 0, 5], [1, 2, 4, 3, 0], [3, 3, 0, 4, 2], [1, 3, 4, 5, 3]]

def printMaze(arr):
    for i in range(Row):
        for k in range(Col):
            print("%3d" % arr[i][k], end = ' ')
        print()
    print()
    
def growRich():
    memo = [[0 for _ in range(Col)] for _ in range(Row)]
    memo[0][0] = goldMaze[0][0]
    
    colSum = memo[0][0]
    for i in range(1, Col):
        colSum +=goldMaze[i][0]
        memo[i][0] = colSum
    
    rowSum = memo[0][0]
    for i in range(1, Row):
        rowSum += goldMaze[0][i]
        memo[0][i] = rowSum
        
    for row in range(1, Row):
        for col in range(1, len(goldMaze[row])) :
            if (memo[row][col-1]>memo[row-1][col]):
                memo[row][col]= memo[row][col-1]+goldMaze[row][col]
            else: 
                memo[row][col] = memo[row-1][col] + goldMaze[row][col]
                
    retValue = memo[Row-1][Col-1]
    
    print("##메모이제이션##")
    printMaze(memo)
    
    row, col = Row-1, Col-1
    memo[row][col] = 0 
    while row != 0 or col !=0 :
        if row-1>=0 and col-1>=0 : 
            if memo[row-1][col]>memo[row][col-1]:
                row -= 1
            else: 
                col -=1
        elif row-1 <0 and col -1 >= 0 :
            col -=1
        else:
            row -=1
        memo[row][col]=0
        
    print("## 메모이제이션 황금미로길 ##")
    printMaze(memo)
    
    return retValue

print(growRich())

11726번: 2×n 타일링 (acmicpc.net)

내 풀이: 

잘 모르겠어서 냅다 세어봤더니 피보나치 수열과 같아서 금방 풀었다. 

i번째 경우의 수 == i-1번째 경우의 수 + i-2번째 경우의 수.

안 세고도 이 공식이 나오려면 어떻게 생각해야 했을까?

9095번: 1, 2, 3 더하기 (acmicpc.net)

(파이썬 코드)

2839번: 설탕 배달 (acmicpc.net)

1463번: 1로 만들기 (acmicpc.net)

(틀렸습니다.)

(메모리 초과)

(시간 초과)

(런타임 에러)

(맞은 풀이)

(수정)

9625번: BABBA (acmicpc.net)

<내 풀이>

1. 입력

입력 값 k를 정수형으로 입력 받는다. 

2. 초깃값 설정 부분

처음 기계를 발견했을 때, 화면에는 A만 표시되어 있는 상태를 표현한다.

A의 개수를 저장하는 a 리스트에 1  , B의 개수를 저장하는 b 리스트에 0을 넣는다. 

(0번째 시행했을 때 A가 1개, B가 0개 있다는 뜻)

3. for 문 부분--

계산한 A개수와 B개수를 계속 리스트에 넣는 다이나믹 프로그래밍

구해야 하는 것은 버튼을 K번 눌렀을 때, 화면에 표시되는 A와 B의 개수인데,

버튼을 한 번 누를 때마다 B는 BA로 바뀌고, A는 B로 바뀐다고 하였다. 

b는 버튼을 한 번 누를 때마다 a가  b 개 늘어나게 만들고, b의 개수에는 영향을 주지 않는다.

----> 버튼을 한 번 누른 후 a의 개수는 버튼을 누르기 이전 b의 개수와 같다.

a는 버튼을 한 번 누를 때마다 원래 있는 a가 모두 사라지게 만들고, b가 a개 늘어나게 만든다. 

---->버튼을 한 번 누른 후 b의 개수는 버튼을 누르기 이전 b의 개수 + 버튼을 누르기 이전 a의 개수와 같다. 

for i in range(1,k+1):

버튼을 1번 부터 k번까지 누르는 동안

(*여기서 i는 지금까지 버튼을 누른 횟수와 같다)

a.append(b[i-1])

a 리스트에 'i-1번 버튼을 눌렀을 때 B의 개수'를 append 한다

b.append(b[i-1]+a[i-1])

b 리스트에 'i-1번 버튼을 눌렀을 때 B의 개수 + i-1번 버튼을 눌렀을 때 a의 개수'를 append 한다.

4.  출력

k번 버튼을 누르는 for문이 끝난 뒤,

a리스트의 마지막 원소(a[-1])와 b리스트의 마지막 원소(b[-1])를 한 줄로 출력한다. 

<풀이 후>

다른 사람들의 코드를 보니 이것도 피보나치 수열이라고 함. 몰랐다. 그리고

a, b = b , b+a 

이렇게 a(A의 개수)랑 b(B의 개수)를 간단히 재정의 하면서 for문을 돌리면

굳이 리스트에 새로운 수를 계속 추가하지 않아도 되는 문제였다!

<내 풀이>

# 그냥 피보나치 수 구하는 문제

# 어려웠던 점

1. 

for문 범위 제한이 헷갈림. a인지 a-1인지 a+1인지...ㅜ

2. 입력값을 받아서 for문 돌리는 거 자체를 반복적으로 하는데 arr을 전역 배열로 입력 받기 전에 넣어버려서 자꾸 그 전 입력 때 추가된 arr에다가 다음 입력때도 값을 더 추가하고 있었음. 

arr은 input 받고 for문 시작하기 전에 넣어서 해결함. 

1. 큰 문제를 작은 문제로 나눌 수 있을 때

2. 근데 작은 문제에서 구한 정답이 큰 문제에서도 동일할 때

3. 그 작은 문제를 반복적으로 계산하지 않고 어딘가에 저장해두었다가 계속 사용하는 것

--> 메모리를 약간 더 사용함으로써 중복 연산을 줄여, 수행속도를 비약적으로 개선하는 방법. 

ex) 피보나치 수열 계산

# 재귀함수 이용= 탑 다운 방식

# 단순 반복문 이용= 보텀 업 방식

(재귀함수보다 반복문을 사용하면 오버헤드를 줄일 수 있다고 함)

유튜브 '개발자로 취직하기' , 이것이 코딩테스트다 with 파이썬을 참고하였음.

#

이차원 리스트를 구현하는 게 익숙하지 않아서 힘들었다.

#

일단 arr이라는 리스트에다가 0이 14개 씩 들어있는 리스트를 15개 추가했다. 

이유는 층수는 0층부터 14층, 호수는 1호부터 14호까지 있다고 했기 때문이다.

0층 호수에 사는 사람의 수는 문제에서 알려주었으므로

arr[0]은 1호부터 14호까지, 1~14가 들어간 리스트로 만들어준다.

이제 1층부터 14층까지의 arr[i][j]즉 거주민 수를 구하는 공식은

arr[i][j]=arr[i-1][j]+arr[i][j-1]이다. 

바로 아래층 같은 호수에 사는 사람 수

+ 아랫층 1호부터 바로 전 호수까지 사는 사람 수의 합(==같은 층의 전 호수, 옆집에 사는 사람 수)

그다음에 입력값 받아서 출력을 하면 되는데 왜 arr[k][n]이 아니라 arr[k][n-1]을 출력한 걸까?

0번째부터 시작하는 리스트의 관점에서는 n호가 n-1호이기 때문. 

ex) 3호 = 세번째 집= arr[k][2]

그래서 n-1로 쓰면 딱 정확하다.

이게 최선일 리가 없는데 다른 사람들이 푼 건 아직 못 살펴봤다.