밤이 블로그

BOJ#1890 점프 * 문제https://www.acmicpc.net/problem/1890 * 풀이dp + dfs로 풀었습니다.정답 비율에 비해 문제가 굉장히 쉽습니다. N 범위와 경로의 개수 범위(long)만 주의하면 될 것 같습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231890/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static final int[] dRow = {0, 1}; stat..

BOJ#2167 2차원 배열의 합 * 문제https://www.acmicpc.net/problem/2167 * 풀이단순하게 for loop 2개로 (i, j) ~ (x, y) 원소들을 더해도 되지만계산량을 줄이기 위해서 아래와 같이 구현해보았습니다. 1. 입력을 받으면서 dp[row][col]를 계산해 놓는다.dp[row][col] : (row, 1) 부터 (row, col)까지의 합 2. K개의 쿼리를 입력 받는다. (i, j), (x, y) 3. 행 단위로 합을 구하고 sum 변수에 합산한다. for ( row = i ... x) { sum += dp[row][y] - dp[row][j - 1];} * 나의 코드https://github.com/stack07142/BOJ/blob/6ac31273349..

BOJ#9084 동전 * 문제https://www.acmicpc.net/problem/9084 * 풀이참고한 블로그 : http://wootool.tistory.com/177http://blog.naver.com/PostView.nhn?blogId=occidere&logNo=220793012348http://heygyun.tistory.com/46 동적계획법의 개념(복잡한 문제를 여러 하위 문제로 나누어 푼다)을 잘 생각해봅시다.dp[i] : 주어진 동전을 가지고 금액 i를 만드는 경우의 수 예를 들어 목표 금액이 30원이고, 동전이 5원, 10원짜리가 있을 때 일단은 5원짜리만 있다고 가정했을 때 dp[30] : 5원짜리로 30원을 만드는 경우의 수이제 10원짜리 동전을 추가해보자. dp[30] : 3..

BOJ#14501 퇴사 * 문제https://www.acmicpc.net/problem/14501 * 풀이2017년 상반기 삼성전자 SW 역량테스트 기출문제입니다. dp 문제입니다. 각 경우(상담)에 대해 상담하는 경우, 상담하지 않는 경우 2가지 경우로 나눌 수 있습니다. 정의 및 점화식dp[idx] : 날짜가 idx 일 때, 이후 얻을 수 있는 금액의 최대값dp[idx] = max(dp[idx+1], dp[idx + T[idx]] + P[idx]) * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2314501_Retire/src/Main.java import java.io.BufferedReader; import java.io.IOException..

BOJ#1670 정상 회담2 * 문제https://www.acmicpc.net/problem/1670 * 풀이 Dynamic Programming 문제입니다. 동적계획법은 복잡한 문제를 하위 문제로 나누어 푸는 것을 말합니다. 이 문제에서는 그림을 그려보면 이해하기 쉽습니다. 예를 들어 N = 6일 때, 아래 3가지 경우의 합을 구하면 되겠습니다. 1) 0번째 사람과 1번째 사람이 악수하는 경우dp[6] += dp[0] + dp[4](한쪽 구역은 0명, 다른 구역은 4명) 2) 0번째 사람과 3번째 사람이 악수하는 경우dp[6] += dp[2] + dp[2](한쪽 구역은 2명, 다른 구역은 2명) 3) 0번째 사람과 5번째 사람이 악수하는 경우dp[6] += dp[4] + dp[0](한쪽 구역은 4명, ..

BOJ#2196 로봇 조종하기 * 문제https://www.acmicpc.net/problem/2169 Olympiad > 한국정보올림피아드 > KOI 2002 > 고등부 1번 * 풀이 꽤 어려운.. 문제인 것 같습니다.풀이는 다른 블로그에 자세히 나와 있으니, 저는 제가 어떻게 생각을 했는지 써보겠습니다. 1. 처음 한 생각은 Backtracking 입니다. 의외로 쉽게 풀릴 것 같습니다.2. 인풋값의 사이즈를 봅니다. 1000 * 1000 사이즈면 Backtracking 형식으로는 풀 수 없을 것 같습니다. (시간 초과)3. Dynamic Programming으로 방향을 잡습니다. 4. dp를 정의합니다. dp[i][j] : (1, 1)에서 (i, j)에 도달할 때 최대 비용5. 왼쪽, 오른쪽, 아래..

BOJ#2565 전깃줄 * 문제https://www.acmicpc.net/problem/2565 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2007 > 초등부 4번 * 풀이 문제 : 전깃줄이 교차하지 않기 위해 없애야 하는 전깃줄의 최소 개수를 구하시오. 문제에서 표시된 위 지문과 같이 전깃줄을 '제거'하는 관점에서 접근하게 되면 문제를 풀기 어려워지게 됩니다. 전깃줄을 하나씩 '제거'하면서 최소한 몇개를 제거해야 하는지 생각하는 것 보다,전깃줄을 하나씩 '추가'하면서 최대한 몇개까지 겹치지 않고 추가할 수 있는지 생각해 봅시다. * 전깃줄이 겹치지 않을 조건 : A를 기준으로 정렬했을 때, B가 순차적으로 나열되어 있으면 된다. 주어진 입력을 A 기준으로 정렬해보면 LIS의 형태가 ..

BOJ#1932 숫자삼각형 * 문제https://www.acmicpc.net/problem/1932 * 풀이 ▷ dp 정의dp[i][j] : i층에서 j 를 선택했을 때, 0~i 층의 최대값 ▷ dp 점화식dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j+1]) 별로 어렵지 않은 문제였지만 시간초과로 고생을 좀 했습니다. 원인으로는 dp 초기값을 0으로 설정했는데 코드 64라인에서 dp값을 재활용 할 때, 원래 삼각형 값이 0인 경우와 dp 초기값 0인 경우를 구분하지 못해서 메모이제이션을 하지 못했기 때문입니다. dp 초기값을 -1으로 고쳐서 해결하였습니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/..

BOJ#1149 RGB거리* 문제https://www.acmicpc.net/problem/1149 * 풀이 ▷ 규칙 - 각 집은 R, G, B 3가지 색 중 한가지 색으로 칠한다. - 이웃한 집은 같은 색으로 칠하지 않는다. - 마지막 집은 R, G, B 3가지 색 중 하나이다. - 위 3가지 경우 중 최소값이 우리가 원하는 정답이다. ▷ dp 정의dp[i][RED] : 0~i 번째 집까지 색칠했을 때 + i번째 집이 RED일 때 costdp[i][GREEN] : 0~i 번째 집까지 색칠했을 때 + i번째 집이 GREEN일 때 costdp[i][BLUE] : 0~i 번째 집까지 색칠했을 때 + i번째 집이 BLUE일 때 cost ▷ 점화식dp[i][RED] = min(dp[i-1][GREEN], dp[i..

BOJ#9251 LCS* 문제https://www.acmicpc.net/problem/9251 LCS(Longest Common Subsequence, 최장 공통 부분 수열) * 풀이 2개의 문자열의 공통 부분 문자열의 길이를 구하는 문제입니다.ex) abcd, bd 일 때 -> 공통 부분 문자열은 bd이고 길이는 2 dp 정의는 아래와 같고 dp[i][j] : s_1, ... , s_i와 t_1, ... , t_j에 대한 LCS의 길이 s_1, ... , s_i+1와 t_1, ... , t_j+1에 대해서 1) s_i+1 = t_j+1 이라면dp[i+1][j+1] = dp[i][j] + 1 2) s_i+1 != t_j+1 이라면dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])..