아리곤듀의 개발 성장 일기

- 문제:

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

- 코드: 

(01.27) 처음에 dp 방식으로 풀지 않고 구현하려하다 봉변당했다.., DP 문제 유형 잘 익히자. 이 글도 한번 날라가서 다시쓰는중ㅠㅠ 화이팅..

조건 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

을 참고하여 점화식 발굴

 dp[i]=max(dp[i-3]+s[i-1]+s[i], dp[i-2]+s[i])

dp[0] 일 경우는 1칸을 갔을 경우이다.

--> 1칸을 가기위해서는 단 하나의 경우 밖에없다.

dp[1] 일 경우는 2칸을 갔을 경우이다.

--> 2칸을 가기위해서는 1칸+1칸 갔을 경우와 한번에 2칸을 갔을 경우로 나눌수 있다. 이 두경우 중 최대값을 저장한다.

dp[2] 일 경우는 3칸을 갔을 경우이다.

--> 3칸을 가기위해서는 1칸+2칸 갔을 경우와 2칸+1칸 갔을 경우로 나눌수 있다. 이 두경우 중 최대값을 저장한다.

n = int(input())
arr = []

for _ in range(n):
    arr.append(int(input()))
    
dp[0] = arr[0]
dp[1] = max(arr[0] + arr[1], arr[1]) # 두칸 올라갔을때 최대
dp[2] = max(arr[1]+arr[2],arr[0] + arr[2])  # 세칸 올라갔을때 최대

for i in range(3, n):
    dp[i] = max(arr[i] + arr[i-1] + dp[i-3], arr[i] + dp[i-2])

print(dp[n-1])

- 문제:

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

- 코드:

 실버라인 DP 문제가 다 어려워서 브론즈 1 단계인 DP를 풀어보았다. 처음에 재귀함수를 시도했는데 실패하고 while 문을 써서 2수가 될때까지 돌아가게 설정했다. 

a = input()
b = input()

arr = []
s = []
        
for i in range(8):
    arr.append(a[i])
    arr.append(b[i])

while len(arr) != 2:
    for i in range(len(arr)-1): # 0~16
        s.append(str((int(arr[i]) + int(arr[i+1]))%10))
    arr = s
    s = []
    
print(''.join(i for i in arr))

- 문제: 

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

- 코드:

하.. DP 언제쯤 내머리로 풀릴래. 감 잡을것 같으면서도 항상 어려운 DP

이 문제는 문제의 패턴을 찾으면 풀 수 있었다. 어떤 규칙성이 보이면 시간이 더 걸리더라도 패턴을 먼저 찾기 위해 노력하자.

1 -> 1개

2 -> 2개

3 -> 4개

4 -> 7개

5 -> 13개

6 -> 21개

7 -> 44개 순으로 되므로

점화식: (n>3) f(n) = f(n-1) + f(n-2) + f(n-3)

def sol(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return sol(n-1) + sol(n-2) + sol(n-3)
        
 n = int(input())

for i in range(n):
    a = int(input())
    print(sol(a))

01.19

- 문제: 

https://itcrowd2016.tistory.com/84

- 풀이:

큰 전체 삼각형에서 작은 삼각형을 빼서 넓이를 구하는 것으로 생각했다. 처음엔 단순히 저 예제에만 적합한 코딩을 해서 애를 먹었다. 최소 최대로만 값을 구해서 계산했었는데 그렇게 풀면 아래와 같은 예제는 조건이 충족되지 않는다. 따라서 참외밭은 ㄱ자 모양이나 ㄴ자 모양, 출발 꼭지점의 시작점은 어디서든 가능, 반시계 방향으로 돎을 따져서 생각해야한다. 

최대로 가장 긴 가로 세로에 붙어있는 양 옆의 변 길이를 구해서 빼는 방식으로 구현해보았다. 그런데 런타임 에러가 나서 확인해보니 %6을 붙여주면 에러가 나지 않았다. 인덱스가 6이상이면 에러가 날뿐만 아니라 시작점을 알 수 없는 상태니 6이내의 값으로 구해야하기 때문이다. 

n = int(input())

bat = [list(map(int, input().split())) for _ in range(6)]

w = 0; w_idx = 0
l = 0; l_idx = 0
for i in range(len(bat)):    
    if bat[i][0] == 1 or bat[i][0] == 2:
        if w < bat[i][1]:
            w = bat[i][1]
            w_idx = i
    elif bat[i][0] == 3 or bat[i][0] == 4:
        if l < bat[i][1]:
            l = bat[i][1]
            l_idx = i
            
 # 가장 긴 각 세로변과 가로변에 붙어있는 가로 세로를 절대값으로 빼면 작은 사각형의 세로와 가로를 구할 수 있음

W = abs(bat[(w_idx-1)%6][1] - bat[(w_idx+1)%6][1])
L = abs(bat[(l_idx-1)%6][1] - bat[(l_idx+1)%6][1])  # %6을 안해주니까 런타임 에러가 났다. 인덱스가 6보다 크면 안되고 어떤 점에서 시작할지 모르기때문에 %6을 넣어야한다

print(((w*l) - (W*L))*n)

- 문제:

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

- 내 코드:

(1.19 목) 쫄지마 쫄지마!!! 할 수 있어 유 캔 두잇 

못 풀 거같아서 먼저 발부터 빼기 금지. 이번주는 그리드 실버 2 문제 2개를 풀어보쟈

n = int(input())

hi = list(map(int, input().split()))
ai = list(map(int, input().split()))

arr = []
total = 0

arr = [[hi[i],ai[i]] for i in range(n)]
arr.sort(key = lambda x:x[1]) #  성장속도가 1에 해당하는 값 기준으로 정렬

for i in range(n):
    total += arr[i][0] + arr[i][1] * i
#     print(total)
print(total)

- 문제:

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

-내 코드:

(01.16) DFS/BFS 그래프 문제 중 DFS는 감이 잡히기 시작했다..! 실버 3까지는 풀어볼만 한 거 같당 

n, k = map(int, input().split())

graph = [int(input()) for _ in range(n)]

a = graph[0]

arrlist = []

for _ in range(n):
    arrlist.append(a)
    b = graph[a]
    arrlist.append(b)
    a = graph[b]
    
if k in arrlist:
    print(arrlist.index(k) + 1)
else:
    print('-1')

- 문제: dfs/bfs 그래프 

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

- 코드:

정답코드를 보면서 dfs, bfs 방식이 어떻게 적용되는지 공부했다. dfs는 재귀함수(깊이), bfs는 큐(넓이)를 사용해서 진행된다. 

# dfs

n = int(input())
net = int(input())

graph = [[]*n for _ in range(n+1)]
for _ in range(net):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

cnt = 0
visited = [0]*(n+1)

def dfs(start):
    global cnt
    visited[start] = 1
    for i in graph[start]:
        if visited[i]==0:
            dfs(i)
            cnt +=1
 
dfs(1)
print(cnt)

# bfs

n = int(input())
net = int(input())

graph = [[]*n for _ in range(n+1)]
for _ in range(net):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

cnt = 0
visited = [0]*(n+1)

def bfs(start):
    global cnt
    visited[start] = 1
    queue = [start]
    print(queue)
    while queue:
        for i in graph[queue.pop()]:
            print(queue)
            if visited[i]==0:
                visited[i]=1
                print("visited: %s"%visited)
                queue.insert(0,i)  # queue 배열 맨앞에 놓기
                cnt +=1
 
bfs(1)
print(cnt)

- 문제:

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

- 내 풀이:

 (01.12) DFS/ BFS 그래프 문제이나 문제를 이해하니까 구지 그 방식이 아니여도 풀 수 있을 것 같아서 EW가 있을 경우 카운트 하도록 문제를 풀었다. DFS/ BFS 공식 문제는 이번주 숙제로 풀어봐야겠다!

n = int(input())
mapp = input()

cnt = 0
for i in range(1, n):
    if mapp[i] == 'W':
        if mapp[i-1] == 'E':
            cnt +=1
        
print(cnt)

- 문제:

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

(1/10) 문제 이해하는데도 오래걸려서 포기하려고 했던 문제,, 2번 정도 보고 완벽히 아니고 대충 이해가 갔다! 

(1/11) 이해 완료~

- 코드: 

정답 코드 중에 파이썬이 없어서 자바코드로 먼저 이해했다.

<코드 이해 돕기 위한 설명>

100 200 300으로 정렬한 뒤에 1번 퀘스트를 진행하면 경험치에서 100을 빼주고, 1번을 진행한 상태니까 100을 어딘가에 한번 더해줄 수 있다.(활성화 된 스톤이 1개니까) 그다음 2번 퀘스트를 진행하면 경험치에서 200을 빼주고, 200만큼을 어딘가에 두번 더해줄 수 있다. (활성화 된 스톤이 2개니까) 이제 3번 퀘스트를 진행하면 경험치를 빼줄 필요 없이 300을 어딘가에 두번 더해주면 된다.

< 내가 이해한 코드와 문제 설명>

"예를 들어서 2,3 번째 아케인스톤이 활성화되어있고(2개가 활성화 되어있네! 그럼 해당 퀘스트를 제외하고 다른 아케인스톤에 해당 퀘스트의 경험치를 2번 뿌릴 수 있음) 첫번째 퀘스트를 진행했을 경우, 첫번째 아케인스톤을 획득하고 2,3번째 아케인스톤에 첫번째 퀘스트의 경험치가 쌓이고 첫번째 아케인스톤 경험치는 0이 된다."

즉, 진행한 퀘스트에 따른 아케인스톤 경험치가 0이 되므로 감소되는 경험치를 최소화하기 위해서는 오름차순으로 정렬해주는 것이 맞다. 퀘스트별 아케인스톤 경험치는 다른 아케인스톤에 본인 경험치를 줄 수가 있는데 활성화 개수에 따라 몇번 줄 수 있는지 달라진다. 그리고 경험치를 주면 본인이 가지고 있던 경험치는 0이 되게한다.

import java.util.Arrays;
import java.util.Scanner;

public class TemplateA {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int quest = scan.nextInt();	
		int activeS = scan.nextInt();
		
		int [] arr = new int [quest];
		
		for(int i = 0; i < quest; i++) {
			arr[i] = scan.nextInt();
		}
		
		Arrays.sort(arr);
		//오름차순으로 정렬해주어 최대 아케인스톤이 활성화 전까지
		//감소되는 경험치를 최소화한다. 
		
		int count = 0;
		//count는 최대 활성 아케인스톤 값까지 증가할 변수
		int exp  = 0;
		//최대 경험치가 들어갈 변수
		for(int i = 0; i < quest; i++) {
			if(count < activeS) {
				count ++;
				//최대 아케인 스톤값이 될때까지 하나씩 더해줌
				exp -= arr[i];				
				//최대 아케인 스톤 값이 되기 전까지는 하나의 경험치가 사라지게
				//됨으로 그 아케인 스톤의 경험치를 총경험치에서 빼줌
				
			}
			exp += (arr[i] * count);
			//이후 활성화된 아케인 스톤의 수와 경험치를 곱해줌
		}
	
		System.out.println(exp);
}
  
	}

- 코드 이해 후 파이썬으로 구현

n, act = map(int, input().split())

k = list(map(int, input().split()))
k.sort()  # 감소되는 경험치 최소화

cnt, exp = 0, 0
for i in range(n):
    if cnt< act:
        cnt+=1
        exp -= k[i]
    exp += k[i] * cnt
print(exp)

❤문제

유형: DP

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

❤코드

t = int(input())

num = 0
for _ in range(t):
    k = int(input())
    n = int(input())
    k0 = [x for x in range(1,n+1)]
    for a in range(k):
        for b in range(1,n):
            k0[b] += k0[b-1]
    print(k0[-1])

상향식으로 풀었당 - 배열에 계속 저장하면서 올라가도록