본문 바로가기

전체 글159

[백준/Java/DP] 10844번: 쉬운 계단 수 문제 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 참고 (1) mygumi.tistory.com/260 백준 10844번 쉬운 계단 수 :: 마이구미 이 글은 백준 알고리즘 문제 10844번 "쉬운 계단 수" 를 풀이한다. 풀이 방법으로는 동적계획법으로 설명한다. 문제 링크 - https://www.acmicpc.net/problem/10844 45656이란 수를 보자. 이 수는 인접한 모든 �� mygumi.tistory.com dp[N][L] = dp[N-1][L-1] + dp[N-1][L+1] → 길이가 N일 때, 마지막 수가 L일 경우의 계단 수 L = 0 → .. 2020. 10. 9.
[Java/백준/DP] 1463번: 1로 만들기 문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 코드 매번 새 유형 나오면 모르쇠,,,,, 슬프다. 우선 초기값, Working-backward는 dp[0]과 dp[1]은 연산을 하지 않아도 되므로 0이다. N==2 : N/2를 하거나 N-1를 하면 바로 1이 된다. → 연산 결과 1번 N==3 : N/3을 하면 바로 1이다 → 연산 결과 1번 N==4 : 3가지 경우의 수를 고려한다. ① N-1 N-1을 하면 N=3 → N/3=1 (연산 결과 2번) ② N/2 N/2를 하면 N=2 → N/2=1 (연산 결과 2번) ③ N/3 N%3!=0 이므로 연산 불가능 ①, ②.. 2020. 10. 5.
[Java/백준/DP] 2579번: 계단 오르기 문제 www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 참고 www.youtube.com/watch?v=EKHFu9vB-Oc 문제에 대한 풀이는 아니지만 계단오르기 문제 유형에 대한 감을 잡기에 좋았다. 코드 한칸 또는 두칸을 이동하는 것, 최댓값을 구하는 것은 어렵지 않았지만 연속된 세 개의 계단을 밟으면 안된다는 조건이 까다롭다ㅠ 가장 마지막 계단 N번째 계단으로 생각해본다. 그 전의 N-1번째 계단을 밟고 올라왔는지, N-2번째 계단을 밟고 올라왔는지로 나눠 계산할 .. 2020. 10. 5.
[Java/백준/DP] 1932번: 정수 삼각형 문제 www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 코드 한 줄과 그 위의 줄만을 생각한 점화식을 세웠다. 0 0 0 0 0 0 ← i=0 0 7 0 0 0 0 ← i=1 0 3 8 0 0 0 ← i=2 0 8 1 0 0 0 ← i=3 0 2 7 4 4 0 ← i=4 0 4 5 2 6 5 ← i=5 == N ↑ ↑ j=0 j=5 입력값을 받는 배열이 triangle, 최대값이 들어가는 배열이 max_triangle이라 할 때, max_triangle[i][j] 에 들어가는 배열을 생각하면 1) 윗 줄의 양 대각선 위치의 max_.. 2020. 10. 4.
[Java/백준/DP] 1149번: RGB거리 문제 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 코드 나한테 미지의 세계인 문제였다.... DP는 문제 맞닥뜨릴 때마다 이게 뭔데 하게 됨 ㅠ 코드는 아래 링크를 참고했다. m.blog.naver.com/occidere/220785383050 [백준] 1149 - RGB거리 (2017-12-02 수정완료) 문제 링크 : https://www.acmicpc.net/problem/1149 이 문제는 아주 전형적인 DP(동적 계획법) 문.. 2020. 10. 2.
[Java/백준/DP] 9461번: 파도반 수열 문제 www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 � www.acmicpc.net 코드 n==1일 때 부터 5까지는 예외이다. → 따로 Basic case인 걸로 했다. 그 이후 점화식은 D(n) = D(n-1) + D(n-5) 이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.Outp.. 2020. 10. 1.
[Java/백준/DP] 1904번: 01타일 문제 www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 코드 IDE에서는 StackOverflowError가 나오지만 백준에서는 정답 뜨는 마성의 코드... DP에 대해 감을 잘 못 잡아서 동빈나 유튜브로 미리 공부하고 시작했다. 내가 생각한 풀이 방법은 Basic case에 대해서 생각한다. (이 코드에선 n이 1, 2일 때) : 재귀함수를 끝내는 역할 값들을 중간 중간 저장해주는 역할의 배열 (dp_arr) : 구한 값을 배열에 저장해주었을 때, 그 값을 다.. 2020. 10. 1.
[Java/백준/DP] 1003번: 피보나치 함수 문제 www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 실패 코드(시간초과) 초과 뜰 것 같긴 했다 ㅎ... import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; class Main{ static long[] zerone = new long[2]; public static long fib(int n) { if(n==0) { zer.. 2020. 9. 30.
[Java/백준/DP] 2748번: 피보나치 수 2 문제 www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된�� www.acmicpc.net 코드 틀렸습니다가 자꾸 떠서 속상했는데 알고보니 결과값이 int형의 범위를 넘어가기 때문이었다. 안심^^ import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputS.. 2020. 9. 25.

티스토리툴바