밤이 블로그

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

BOJ#2089 -2진수 * 문제 https://www.acmicpc.net/problem/2089 * 풀이 기존에 10진수를 2진수로 변환하는 알고리즘과 같이주어진 수를 (-2)로 나누어 가면서, 나머지들을 저장하는 방법을 쓴다. 단, 주의할 점으로는 나머지를 올림 해야 한다는 것이다. * 참고http://kin.naver.com/qna/detail.nhn?d1id=11&dirId=1113&docId=57428826&qb=7Iut7KeE7IiYIOydtOynhOyImCDrs4DtmZgg7JuQ66as&enc=utf8§ion=kin&rank=9&search_sort=0&spq=0 * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%232089_MinusB..

BOJ#1699 제곱수의 합 * 문제https://www.acmicpc.net/problem/1699 * 풀이Dynamic Programming 문제입니다. 주의할 점으로,Greedy 하게 풀면 안됩니다. 반례로 12의 경우를 생각해보시면 되겠습니다.ex) 12 = 3^2 + 1^2 + 1^2 + 1^2 (4) = 2^2 + 2^2 + 2^2 (3) 따라서 동적계획법을 이용하면서 완전 탐색을 해주시면 됩니다. - 비슷한 문제 https://www.acmicpc.net/problem/1463 * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%231699_SumOfSquares

BOJ#13415 정렬 게임 * 문제https://www.acmicpc.net/problem/13415 * 풀이시간 제한 때문에 생각할게 많은 문제입니다.주어진 정렬 Order를 모두 수행하는 경우 시간 초과가 발생하기 때문입니다. 알고리즘 #1. 필요 없는 정렬 Order는 무시한다.ex)104 1 5 2 3 10 8 11 15 663 24 55 43 22 13 1 오름차순을 (+), 내림차순을 (-)라고 했을 때,+3 → -2 → +4 → -5 → +5 → -4 → +3 → -2 → +2 → -1 → +3 → -1 에서+3 → -2 → +4 → -5 → +5 → -4 → +3 → -2 → +2 → -1 → +3 → -1 회색 음영은 수행하지 않아도 되므로결국 +5 → -4 → +3 → -1 으로 줄일..

BOJ#2156 포도주 시식 * 문제https://www.acmicpc.net/problem/2156 * 풀이동적계획법(Dynamic Programming)을 이용해봅시다. 일단 아래와 같이 배열을 선언합니다.dp[n] : n잔 째 마셨을 때, 최대로 마실 수 있는 포도주의 양p[n] : 포도주 n번 째 잔에 들어있는 포도주의 양 포도주는 3번 연속해서 마실 수 없으므로,n번 째 (마지막) 포도주는 3가지 경우로 나눌 수 있습니다.마시지 않는 경우, 1잔 째 마신 경우, 2잔 째 마신 경우 우리가 구하려는 dp[n]을 구해봅시다.1) 마지막 n번 째 포도주 잔 - 마시지 않는 경우 : n-1번 째 잔은 다시 1, 2, 3번의 경우로 나누어 질 수 있습니다. : dp[n] = dp[n-1] 2) 마지막 n..

BOJ#10799 쇠막대기 * 문제https://www.acmicpc.net/problem/10799 * 풀이초등부, 중등부 문제입니다. 어렵지 않고 재밌는 문제인 것 같아요. 저는 일단 입력받은 String에서 ()을 x로 치환했고,이후 Char Array로 변환해서 for loop을 돌렸습니다. 입력값 : (((()(()()))(())()))(()())치환값 : (((x(xx))(x)x))(xx) loop를 돌면서' ( ' 가 나오면 왼쪽 괄호 개수++, 조각 개수++' x ' 가 나오면 레이저 개수++ → 조각 개수 update → 레이저 개수 = 0' ) ' 가 나오면 왼쪽 괄호 개수-- inputStr = br.readLine(); replacedStr = inputStr.replace("()"..

BOJ#11403 경로찾기* 문제https://www.acmicpc.net/problem/11403 * 풀이 가중치 없는 방향 그래프가 행렬로 주어졌을 때, i에서 j로 가는 경로 유무를 행렬로 표현하라. bfs(Breadth First Search)를 이용하였다. 1. bfs(i, j) : i를 시작점으로 해서 연결된 모든 노드를 탐색한다. j를 찾을 경우 return.2. 위 과정에서 탐색한 노드는 중복해서 탐색하지 않도록 한다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2311403_BFS_FindPath/src/Main.java Java (17.08.29)import java.io.*; import java.util.LinkedList;..