밤이 블로그

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#1405 미친 로봇 * 문제https://www.acmicpc.net/problem/1405 * 풀이 - N의 범위가 작으므로 visited 배열을 이용하여 간단하게 단순 경로인지 아닌지 체크해줍니다.- 각 방향으로 움직일 확률을 입력 받을 때, double 타입의 확률로 바꿔서 입력받아줍니다.- 1번 이동해서 단순경로가 된다면 확률은 1.0, 그렇지 않으면 0.0 입니다.- 4방향으로 움직일 수 있으므로4방향 Sum(각 방향으로 움직일 확률 * 현재 위치에서 N-1번 움직일 때 단순경로가 될 확률) * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%231405_CrazyRobot/src import java.io.BufferedReader; i..

BOJ#1339 단어 수학 * 문제https://www.acmicpc.net/problem/1339 * 풀이 이 문제는 두가지 풀이법으로 풀어보겠습니다. 예)MCR ACDEB 1) 수학으로 풀기 위의 두 숫자를 풀어보면MCR = M * 100 + C * 10 + R * 1ACDEB = A * 10000 + C * 1000 + D * 100 + E * 10 + B * 1 두 숫자를 더해보면MCR + ACDEB = 10000A + 1001C + 100M + 100D + 10E + R + B 가 됩니다. 하나의 문자는 하나의 숫자(0~9)로 대응되고합의 최대값을 구하고 싶으므로 즉, 10000A + 1001C + 100M + 100D + 10E + R + B의 최대값을 구하면 되는 것입니다. A -> C ->..

BOJ#12094, BOJ#12100, BOJ#12208, BOJ#12209 2048 * 문제https://www.acmicpc.net/problem/12094https://www.acmicpc.net/problem/12100https://www.acmicpc.net/problem/12208https://www.acmicpc.net/problem/12209 * 2048 게임 링크https://gabrielecirulli.github.io/2048/ * 문제 풀이 순서1. Move(Up, Down, Left, Right) 연산 구현하기BOJ#12208, BOJ#12209 2. N번 Move 이후 최대값 구하기BOJ#12100, BOJ#12094 * 나의 코드 https://github.com/stack07..

BOJ#1707 이분 그래프 * 문제https://www.acmicpc.net/problem/1707 * 풀이 그래프 관련 기본 문제입니다. 저는 BFS/DFS로 풀었는데, 주의할 점으로 연결 그래프와 비연결 그래프를 둘 다 고려해주어야 합니다, * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231707_BipartiteGraph/src/Main.java (BFS)import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /** * BOJ#1707 이분 그래프 * https://www.acmicpc.net/p..

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