은비블로그

[백준] 11726 : 2 x n 타일링 (JAVA)

https://www.acmicpc.net/problem/11726 [풀이과정]전형적인 DP 문제다. 점화식으로 풀면 됨.직접 타일을 그려보면  f(n-1)의 가짓수에 세로 타일을 하나씩 붙이고 + f(n-2)의 가짓수에 가로 타일 2개가 붙은 모양임f(0) = 1, f(1) = 1 이고f(n) = f(n-2) + f(n-1) [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/*2xn 크기의 직사각셩을 1x2,2x1 타일로 채우는 방법의 수 구하기 */public class Main { static BufferedReader br = new BufferedReader(new Inp..

https://www.acmicpc.net/problem/30470 [풀이과정]stack을 사용하였고 max가 갱신될 때마다 stack에 저장된 값들을 확인하면서 길이를 갱신하며 pop, push를 해주었는데 틀림. 로직은 맞는 것 같은데 왜 틀린지 잘 모르겠음.정답코드는 max 갱신 시마다 값을 확인하는 로직을 없앰. 새로 추가되는 통나무가 항상 제일 긴 통나무이고 max 값을 기준으로 통나무 길이가 갱신되는 것이기 때문에 max값만 저장해준 후 sum 값을 구할 때 로직 실행해켜주면 됨. [코드]import java.io.*;import java.util.*;public class Main { static BufferedReader br = new BufferedReader(new InputSt..

https://www.acmicpc.net/problem/2631 [풀이과정]전형적인 LIS 문제였다. N이 200으로 작아서 O(N^2)인 DP 방식으로 풀이했음.N이 커지면 O(nlogn)인 이분탐색으로 풀이해야 한다. 현재 탐색 중인 번호의 이전 번호들을 보면서 더 크면 DP[현재 번호] = DP[이전 번호 중 가장 큰 값을 가진 번호] + 1을 해주는 것  [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;/*N명의 아이들1번부터 N번. 옮기는 순서를 최소로 하여 일렬로 정렬 */..

https://www.acmicpc.net/problem/22869 [풀이과정]단순히 도달여부를 확인하기만 하면 되는 문제.O(N^2)이 2500만이어서 DFS로 풀었다가 시간초과가 발생했다. 단순히 N^2이 아닌 실제로 호출되는 함수가 컸던 부분이 원인이었음.DP를 이용해서 도달 가능한 부분만을 true로 삼아 경로를 확인하는 방식으로 호출 횟수를 줄임. [코드]import java.util.*;import java.lang.*;import java.io.*;/*사용하는 힘은 항상 양수.오른쪽으로 갈 때 사용해야 하는 힘이 K가 넘지 않을 때 이동 가능끝까지 도착이 되는지의 유무 계산*/class Main { static BufferedReader br = new BufferedReader(new..

https://www.acmicpc.net/problem/15989 [풀이과정]DP[n][1] : 1로 끝나는 수식 개수 [1]1DP[1][1] = 1 [2]1+12DP[2][1] = 1DP[2][2] = 1 [3]1+1+11+23DP[3][1] = 1DP[3][2] = 1DP[3][3] = 1 [4]1+1+1+11+1+22+21+3DP[4][1] = 1DP[4][2] = 2 -> 1+1, 2 (DP[2][1], DP[2][2])DP[4][3] = 1 -> 1(DP[1][1])...[6]1+1+1+31+2+33+3DP[6][3] = DP[3][1] + DP[3][2] + DP[3][3] 점화식DP[i][1] = DP [i-1][1];DP[i][2] = DP[i-2][1] + DP[i-2][2];DP[i]..

https://www.acmicpc.net/problem/15988 [풀이과정]모듈러 연산의 분배법칙 : 처음부터 끝까지 모두 더하고 % 연산을 하기 == 더하는 중간중간 % 연산을 하기즉, (A+B+C...) % n == ((A%10) + (B%10) + (C%10) + ...) % n N이 3미만 일 때 고려DP[1], DP[2], DP[3]는 직접 초기화하기 때문에 값이 3보다 작으면 런타임에러 발생 [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/*정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성 */public class Mai..

https://www.acmicpc.net/problem/12101 [풀이과정]정수 4를 1,2,3의 합으로 나타내는 7가지 방법을 사전순으로 정렬 1. 1+1+1+12. 1+1+23. 1+2+14. 1+35. 2+1+16. 2+27. 3+11을 만드는 경우 12를 만드는 경우 1+1 / 23을 만드는 경우 1+1+1 / 1+2 / 2+1 / 34를 만드는 경우1+31+1+22+21+1+1+11+2+12+1+13+1i = 1, 2, 3n-i엔 +i를 끝에 붙여주기.[코드]paimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.u..

https://www.acmicpc.net/problem/9095 [풀이과정]점화식 -> DP[n] = DP[n-1] + DP[n-2] + DP[n-3]; (n >= 4)DP[1] = 1, DP[2] = 2, DP[3] = 4 임.  1) 1을 만드는 경우1 2) 2를 만드는 경우1 + 12 3) 3을 만드는 경우1 + 1 + 11 + 22 + 13 4) 4를 만드는 경우 -> DP[1] + DP[2] + DP[3]1 + 31 + 1 + 22 + 21 + 1 + 1 + 11 + 2 + 12 + 1 + 13 + 1 5) 5를 만드는 경우 -> DP[2] + DP[3] + DP[4]1 + 1 + 12 + 11 + 1 + 1 + 11 + 2 + 12 + 1 + 13 + 11 + 3 + 11 + 1 + 2 + ..

https://www.acmicpc.net/problem/2240 [풀이과정]3차원 DP로 풀었다.for( 1 -> T ){ for( 1 -> W+1 ){ 매초마다 해당 시간에 떨어지는 열매 1. 1번 나무로 떨어질 때 1-1. 해당 위치로 이동해서 1-2. 그대로 2. 2번 나무로 떨어질 때 2-1. 해당 위치로 이동해서 2-2. 그대로 }}  *W+2로 초기화한 이유는 w = W+1일 때, W번 이동했을 경우를 계산할 수 있기 때문이다. [코드]import java.io.*;import java.util.StringTokenizer;/*매 초마다 두 개의 나무 중 하나의 나무에서 자두가..

https://www.acmicpc.net/problem/2660 [풀이과정]문제 이해가 힘들었다. 그래프로 바꿔 생각하면직접 친구 = 거리 1친구의 친구 = 거리 2이런 식이었다.각각의 후보(노드)는 가장 먼 친구의 점수(거리)이고회장은 그 중 점수가 가장 작은 후보이다.이때 같은 점수를 가진 모든 후보를 출력해야 했음. 모든 정점 쌍 간의 최단 거리를 구해야 했기 때문에 플로이드 와샬 알고리즘을 사용했다. [코드]import java.io.*;import java.util.StringTokenizer;/*각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 됨.다른 모든 회원과 친구이면 1점다른 모든 회원과 친구 || 친구의 친구이면 2점다른 모든 회원과 친구 || 친구의 친구 ||친구의 친구의 ..