밤이 블로그

BOJ#2532 먹이사슬 (Chain) * 문제https://www.acmicpc.net/problem/2532 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2012 > 중등부 3번 * 풀이Tip #1) 공식 풀이는 한국정보올림피아드 홈페이지에서 볼 수 있습니다.Tip #2) 더블릿(http://www.dovelet.com)에서 채점하면 테스트케이스를 볼 수 있습니다.Tip #3) LIS 문제입니다. LIS 관련해서는 아래 문제들을 먼저 풀어보는 것을 추천드립니다.-가장 긴 증가하는 부분 수열 (https://www.acmicpc.net/problem/11053)-전깃줄 (https://www.acmicpc.net/problem/2565) 이 문제의 입력값 중 동물의 번호는 필요가 없습..

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

BOJ#2252 줄 세우기 * 문제https://www.acmicpc.net/problem/2252 * 풀이 어떤 일에 선/후 관계나 순서가 있으므로 위상 정렬을 이용해보았습니다. -> 위상 정렬 설명 : http://navercast.naver.com/contents.nhn?rid=2871&contents_id=91824 주의할 점으로는32000 * 32000 배열이 선언이 안되므로 (Heap 사이즈)ArrayList를 사용했습니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%232252_Lineup/src import java.io.*; import java.util.*; /** * BOJ#2252 줄세우기 * https://www.acmic..

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])..

BOJ#6195 Fence Repair * 문제https://www.acmicpc.net/problem/6195 (Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO November 2006 Contest > Gold 1번) * 풀이 최초 생각한 알고리즘은 가장 긴 널빤지를 가장 빨리 만드는 것이었습니다.(늦게 처리할 수록 큰 값이 Cost에 포함되기 때문에) 그러나, 위 알고리즘의 반례는 아래와 같습니다. ex) 5 / 1, 2, 3, 4, 5 일 때 1단계 : 15 -> 5, 10 (15)2단계 : 10 -> 4, 6 (10)3단계 : 6 -> 3, 3 (6)4단계 : 3 -> 2, 1 (3) Cost : 34 1단계 : 15 -> 7, 8 (..

BOJ#7676 Saruman's Army * 문제https://www.acmicpc.net/problem/7676 (University > Stanford Local ACM Programming Contest > SLPC 2006 1번) * 풀이 palantir를 가장 적게 배치하는 것이 목적이다.문제에서 주어진 R은 반경이다.(반지름) 1. palantir 범위에 포함되지 않은 가장 왼쪽 점을 포함하는 가장 오른쪽 점을 구하자. (두 점이 같을 수도 있다.)2. 구한 오른쪽 점이 palantir 위치이다.3. palantir 위치를 기준으로 palantir 범위에 포함되지 않은 가장 오른쪽 점을 구하자. 위 알고리즘을 모든 점이 palantir 범위에 포함될 때까지 반복한다. , 풀이는 위와 같고,중..

POJ#3617 Best Cow Line * 문제http://poj.org/problem?id=3617 * 풀이 1.처음 문자와 마지막 문자가 크거나 작은 경우 뿐만 아니라두 문자가 같은 경우도 잘 생각해보아야 한다. 예) GFABFG 2. 문자 수가 80이 될 때마다 new line을 삽입해야 한다.여기서 String의 length를 이용하지 말고 (\n이 length에 포함되므로)loop 횟수를 이용해야 한다. * 나의 코드https://github.com/stack07142/HappyAlgo/tree/master/HappyAlgo%238_BestCowLine/src import java.io.BufferedReader; import java.io.IOException; import java.io.I..

BOJ#1700 멀티탭 스케쥴링 * 문제https://www.acmicpc.net/problem/1700 * 풀이 전기용품 사용 순서가 주어지므로,이를 통해 멀티탭에서 어떤 플러그를 뽑아야 하는지 판단할 수 있다. -> 현재 멀티탭에 꽂혀있는 전기용품 중 가장 나중에 사용되는 전기용품의 플러그를 뽑는다. * 테스트 케이스 2 72 3 2 3 1 2 7 : 2 2 132 3 1 3 1 3 1 3 2 2 2 2 2 : 2 2 153 2 1 2 1 2 1 2 1 3 3 3 3 3 3 : 2 3 81 2 3 4 1 1 1 2 : 1 1 31 2 1 : 2 3 61 2 3 4 1 2 : 1 6 71 1 1 1 1 1 2 : 0 2 101 2 3 2 3 2 2 2 1 2 : 2 5 201 2 3 4 1 1 1 3 ..