SLENDER ANKLES's 개발블로그

그래프의 첫번째 노드에서 출발해서 연결된 서로 연결된 노드들은 모두 감염된다. 

첫 번째 노드가 속하지 않는 그래프에는 감염되지 않는다. 

그렇다면 첫번째 노드가 속한 그룹의 개수를 세면 감염되는 컴퓨터의 수를 알 수 있게 된다. 

인덱스 위치를 앞 뒤로 주고 문제의 규칙에 맞게 인덱스를 옮겨다니며 값을 갱신하고 출력해주는 형식으로 

답을 출력하였다.

front_index, end_index를 이동시켰다. 

규칙

while(front_index != end_index){

1. front_index에서 출력하고 front_index++

2. front_index의 값을 end_index++ 위치에 갱신

3. front_index++해준다.

}

이 조건을 수행해주니까 답이 도출

gcd는 

예를 들어 

8, 28의 최대 공약수를 구해보면

3 = 28 / 8 ...4

2 = 8 / 4 ...0

AB/GCD = GCD*a*b;

결국 AB/GCD는 최소공배수가 된다

[다시 풀었어도 난해한 문제]

오랜만에 드디어 문제가 풀렸다. ㅜㅜ

답이 잘 안 나오는 문제가 너무 많다. 분발하자. 

떡 먹는 호랑이 문제는 내가 너무 어렵게 생각한 거 같다. 

알고 봤더니 쉽고 정말 좋은 문제였다.라고 스스로 평가하고 싶다. 

우선 첫날 준 떡 + 두번째 날 준 떡 = 세번째 날 준떡 이어야 한다는 것은 피보나치 점화식을 가진다는 것을 알 수 있음!

문제에서는 n번째 날에 k의 떡을 준 것을 토대로 문제를 풀어 첫 번째 날과 두 번째 날에 준 떡의 개수를 알아내야 한다. 

처음은 점화식의

f(n) = a*f(n-2) + b*f(n-1) 이라는 식을 세워서 계수를 알아내야 한다고 생각 한다. 물론 맞다.

a와 b를 빼놓고 생각해본다면

f(n) = f(n-2) + f(n-1)이라는 점화식이 나오고

f(1) = 1, f(2) = 1로 놓으면 계수가 나오지 않겠는가!!!

결국 첫날 준 떡 a , 두번째 날 준 떡 b의 계수를 구할 수 있게 된다. 

이 계수를 토대로 a와 b를 구해야 한다. 어떻게?

처음은 다이나믹 프로그래밍으로 풀어야 하나를 생각해보면서 이상한 고민을 했었다. 

하지만 단지 이중 for문을 돌면서 때려 맞추고 break으로 빠져나오면 된다.

심각한 루프를 돌지도 않고 또한 워낙 범위가 많지 않아 무리 없이 수행 할 수 있다.!!!

문제의 조건들을 면밀히 살펴 시간분석도를 대략적으로 계산할 줄 알아야 한다는 생각을 했다. 이 부분을  좀 더 공부해야겠다.

동적계획법 다이나믹프로그래밍을 사용하여 풀 수 있는 문제이다. 

맨 처음은 완전탐색의 방법을 사용하였으나 테스트케이스 9개? 정도 맞추고 시간초과났다.

다이나믹프로그래밍을 쉽게 적용하여 풀 수 있는 문제라는 생각을 해보았다.

점화식은 간단하다.

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + arr[i][j]로써

입력받은 배열을 arr로 놓았고 dp라는 배열을 만들어서 현재까지 지나오면서 채취할 수 있는 자원의 최대양을 저장하는 배열을 하나 더 만들었다. 

for문을 돌면서 현재의 위치에서 경로 중 가장 자원을 많이 채취 할 수 있는 양을 계산해주었다.(이게 가능한 것은 scv가 오른쪽 또는 아래쪽으로만 이동 할 수 있기 때문이다.)

현재의 배열의 위치는 왼쪽에서 진입하는 scv가 채취하는 최대의 양 또는 위쪽에서 진입하는 scv가 채취하는 최대의양을 말한다.