풀이조건부터 살펴보면 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. 1을 뺀다. 위 순서대로 풀려고하면 예외케이스가 많이 나타나게 된다. 그래서 반대로 생각해보면 DP로 풀 수 있는것을 찾을 수 있다. 1. X에 곱하기 3을 한다.2. X에 곱하기 2를 한다.3. 1을 더한다. cnt=3을 만들어 놓고 cnt를 늘려가면서 계산을 해주면 된다. DP[3*cnt] = DP[cnt]+1DP[2*cnt] = DP[cnt]+1DP[1+cnt] = DP[cnt]+1 이렇게 넣어주되 중복될 경우에는 더작은 숫자를 넣어주면 된다. 문제에서 주어진 크기가 1000000 보다 작거나 같은 수이므로 cnt*3 또는 cnt*2 또는 cnt+1이 1000000을 넘지 않도..

풀이순서대로 우선순위가 주어졌을때 가장큰값을 만나면 큰값을 기준으로 왼쪽에 있는 값이 오른쪽끝으로 넘어가게 된다. 1 2 3 4 가 주어졌을 때 4 1 2 34 3 1 24 3 2 1 순으로 정렬하면 되는것을 알 수 있지만 문서의 우선순위가 같은경우를 체크해주기 위해 chk 배열을 만들면 해결할 수 있다. 문제제목이 큐라고 되어 큐를 구현할수도 있겠지만 우선순위에 맞게 위치를 계속 이동해주면서 최종 배열에서 chk값을 확인하여도 풀 수 있다. 순서1. 0번지를 선택하여 가장 큰값을 찾는다.2. 가장큰값의 index부터 n까지 tmp 배열에 저장해둔다.3. 0부터 가장큰값의 index까지 tmp 배열에 저장해둔다.4. 원래 배열에 tmp배열을 대입한다. 위 순서대로 0부터 n까지 루프를 돌면 내림차순으로 ..

풀이문제를 알고리즘 유형에 맞게 바꾸어 해석해보면 다음과 같다. 1. 출발지점은 무조건 1번부터 시작한다. (1번 컴퓨터는 무조건 감염 되어있다.)2. 출발지점부터 그다음 갈 수 있는 지점까지를 카운트 한다. (1번부터 연결되어 있는 컴퓨터를 모두 찾아야 한다.) 이렇게 보면 출발지점이 고정되어 있는 일반적인 BFS 문제와 같다. 만약 2하고 4가 연결되어 있다면 2번지점에 있을때 4번으로 갈 수 있고, 4번지점에 있을때 2번으로 갈 수 있다. (양방향 간선이다.)2차원 배열을 만들어서 연결되어 있다면 1, 없다면 0을 넣어두고 array[컴퓨터1][컴퓨터2] == 1 일때만 큐에 삽입할 수 있게한다.이 때 양방향으로 갈 수 있으므로 array[컴퓨터2][컴퓨터1] == 1 일때도 생각해 주어야한다. 순..

풀이규칙을 알기위해서 수작업으로 어떤 경우의 수가 있는지 탐색합니다. n=1 1n=2 10n=3 100 101n=4 1000 1001 1010n=5 10000 10001 10010 10100 10101n=6 100000 100001 100010 100100 101000 100101 101010 101001 : : 규칙을 보면 1 1 2 3 5 8 ''' 과 같은 익숙한 숫자가 나옵니다. 위 숫자는 피보나치 수로 재귀나 DP로 간단하게 구현할 수 있습니다. 피보나치 수를 재귀로 구현하면 미리 계산한 부분을 또 계산하기 때문에 비효율적이고 시간초과가 날 수 있습니다. 이런 경우 메모이제이션을 통해 구할 수 있습니다. 주의할 점은 피보나치의 수를 구현할 때 n이 47을 넘게 되면 int형의 범위를 넘어가게 됩..

풀이모든 경우의 수를 생각해 보았습니다.n=1 --> 크기1 1개n=2 --> 크기1 2개 or 크기2 1개n=3 --> 크기1 3개 or 크기1 1개 + 크기2 1개 (왼쪽에 배치하였을 때) or 크기1 1개 + 크기2 1개 (오른쪽에 배치하였을 때) : : 규칙을 찾아보면 점화식을 이루는 것을 찾을 수 있습니다.점화식 n = n-1 + n-2 재귀로도 풀 수 있지만 1000까지 재귀로 풀게되면 시간초과가 날 수 있으므로 DP를 이용하여 풀 수 있습니다. 12dp[1] = 1;dp[2] = 2;cs초기값을 미리 지정해줍니다. (피보나치 수열과 비슷합니다.) 1dp[i] = (dp[i - 1] + dp[i - 2])cs다음과 같이 점화식을 쓸 수 있습니다. 문제에서 10007으로 나눈 나머지를 출력하라 ..

DP로 분류된 문제 조건1. 계단을 오를때는 1칸 또는 2칸까지 한번에 오를수있다.2. 연속된 3칸은 오를 수 없다.3. 마지막 계단은 무조건 밟아야한다. 풀이마지막 계단을 무조건 밟아야한다면 두가지로 분류할 수 있다.1. 전칸을 밟고 마지막칸을 밟는 경우 ? ? O O --> 마지막 칸이 n이라면 n-1 + n이 된다. 2. 전전칸을 밟고 마지막칸을 밟는 경우? O X O --> 마지막 칸이 n이라면 n-2 + n이 된다. 하지만 1번의 경우 연속으로 3칸을 밟을 수 없으므로 전칸을 밟고 현재칸을 밟는경우에는 조건을 추가해주어야한다. 1. 전칸을 밟는 경우에는 n-2번째 칸을 밟을 수 없다. (즉, 전전전칸 + 전칸 + 현재칸이 되어야한다.)? O X O O --> n-3 + n-1 + n으로 쓸 수 ..