-

K번째 수 11004https://www.acmicpc.net/problem/11004 [풀이]숫자의 최대 입력 개수가 꽤 크다.수 정렬하기 3번 문제가 생각나서 비슷하게 풀려고 했으나 입력받은 수의 범위가 -10^9 < A < 10^9여서 포기.정렬 하면 분명히 시간초과걸릴텐데.... 하며 고민하던 중퀵소트를 변형해서 풀어보기로 했다. 설명하기가 좀 애매한 관계로 소스코드를 참고해 보자 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.io.BufferedReader;import java.io.InputStreamReader;i..

수 정렬하기 3 10989https://www.acmicpc.net/problem/10989 [풀이 방법]무턱대고 정렬 알고리즘으로 정렬을 시도했다간 시간초과 나기 십상이다. 퀵소트로 해도.그도 그럴것이 정렬해야 하는 숫자의 개수가 최대 10000000개 니까 정렬 말고 다른방법으로 풀어야한다. 여기서 힌트를 얻은 곳은 입력되는 수가 최대 10000이라는 것!크기 100001 짜리 배열 ar을 생성한 후 입력받은 숫자의 인덱스의 값 ar[index]를 1 증가시켜준다. 입력을 다 받았으면 ar[1]부터 ar[10000]까지 해당하는 값 만큼 index를 출력해준다. 1234567891011121314151617181920212223import java.io.*; class Main { public sta..

더하기 사이클 1110https://www.acmicpc.net/problem/1110 [풀이] 문제에 풀이과정이 다 나와있기 때문에 차근차근 문제의 설명을 따라가면 어렵지 않게 풀 수 있다.10의자리와 1의자리를 구하고 left = num / 10 (10의자리) right = num % 10 (1의자리)다음 숫자를 구한 다음 count++해준다. tmp = right*10 * (left+right)%10새로운 숫자의 10의자리와 1의자리를 구한다. ll = tmp/10 rr = tmp%10left 와 ll 그리고 right와 rr이 같은지 체크한 뒤같으면 count 출력같지 않으면 위의 작업 반복해준다. 123456789101112131415161718192021222324252627import jav..

숫자삼각형 1932https://www.acmicpc.net/problem/1932 [문제풀이]작성중 123456789101112131415161718192021222324252627282930313233343536373839import java.io.BufferedReader;import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int row = Integer.par..

계단오르기 2579https://www.acmicpc.net/problem/2579 [문제 풀이] i번째 계단을 밟았을 때 최댓값은 두 경우 - i-2번째 계단 밟고 i번째 밟을 경우 - i-1번째 계단 밟고 i번째 밟을 경우중 최댓값을 고르면 답!!??이 아니라 틀린다!! 2번조건 "연속된 세 개의 계단을 밟으면 안된다"는 조건이 있기 때문이다! 자, 그러면 어떻게 풀어야 할까?일단 2차원 배열을 생성한다. i번째 계단을 밟았을 때 1) 1번 연속으로 밟은 경우 : dp[1][i] 2) 2번 연속으로 밟은 경우 : dp[2][i]두 경우로 나눌 수 있다! 이때, 1) i번째 계단을 1번 연속으로 밟기 위해서는 i-2번째 계단에서 2칸 이동하는 방법밖에 없으므로 dp[1][i] = max(dp[1][i-..

이친수 2193https://www.acmicpc.net/problem/2193 [문제 풀이]자리수 : n dp[i][0] : i자리 이친수 중 0으로 끝나는 이친수의 개수dp[i][1] : i자리 이친수 중 1로 끝나는 이친수의 개수 dp[i][0] = dp[i-1][0]+dp[i-1][1]dp[i][1] = dp[i-1][0] 답 : dp[n][0]+dp[n][1] 1234567891011121314151617181920212223import java.io.BufferedReader;import java.io.InputStreamReader; /* * 2193번 이친수 */public class Main{ static long d[][]; static int n; public static void m..

1로 만들기 1463https://www.acmicpc.net/problem/1463 [풀이방법]dp[i] = i를 1로 만드는 최소 연산 수 dp[i] = min(dp[i-1], dp[i/2], dp[i/3])+1 모든 연산을 마친 후 dp[i]를 출력하면 답! 123456789101112131415161718192021222324252627282930313233import java.util.Scanner;/* * X가 3으로 나누어 떨어지면, 3으로 나눔. * X가 2로 나누어 떨어지면, 2로 * 1을 뺀다. * 범위 : 1 2 -> 1이렇게 4번이 걸린다.

RGB거리 1149https://www.acmicpc.net/problem/1149 [풀이방법]dp[0][i] = i번째에 R을 칠할 때 까지 든 최소비용dp[1][i] = i번째에 G을 칠할 때 까지 든 최소비용dp[2][i] = i번째에 B을 칠할 때 까지 든 최소비용이라고 할 때 dp[0][i] = min(dp[1][i-1], dp[2][i-1])+i번째 R을 칠할때 드는 비용dp[1][i] = min(dp[0][i-1], dp[2][i-1])+i번째 G을 칠할때 드는 비용dp[2][i] = min(dp[1][i-1], dp[0][i-1])+i번째 B을 칠할때 드는 비용 dp[0][i], dp[1][i], dp[2][i] 중 최솟값을 출력하면 된다. 123456789101112131415161718..

피보나치 함수 1003https://www.acmicpc.net/problem/1003 [문제 요약]숫자 n이 주어지고, f(n)을 n번째 피보나치 수라고 할 때, f(n)을 구하기 위해 f(0)과 f(1)이 몇 번 호출됐는지 구하기 입력과 출력 형식은 이렇다. 문제 분류는 DP로 되어있지만 그냥 재귀로 풀어도 시간초과 나지 않고 풀린다... 12345678910111213141516171819202122232425262728import java.io.*; public class Main { static int n1=0; static int n0=0; public static void main(String[] args) throws Exception { // TODO Auto-generated metho..