밤이 블로그

BOJ#14502 연구소 * 문제https://www.acmicpc.net/problem/14502 * 풀이2017년 상반기 삼성 SW 역량평가 기출문제 입니다. 벽을 항상 3개 설치해서 안전영역의 최대값을 구해야 하는 문제입니다.즉, 완전 탐색이 필요합니다. (모든 경우를 다 해봐야 최대값을 구할 수 있음) 저는 아래와 같이 풀어보았습니다. 1. 조합을 돌려서 Map에서 빈칸 3개를 선택한 후 벽으로 바꿔줍니다. 최대 8*8 맵에서 빈칸 3개를 선택할 때 경우의 수 = (64-2)C3(바이러스가 최소 2개 있으므로) 2. 해당 Map에서 바이러스를 퍼뜨립니다. 3. (맵의 크기 - 바이러스의 수 - 벽의 수) 의 최대값을 갱신합니다. 4. 1~3 반복 * 나의 코드 https://github.com/s..

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#1600 말이 되고픈 원숭이 * 문제https://www.acmicpc.net/problem/1600 * 풀이bfs 탐색 문제입니다.일반적인 격자(상,하,좌,우) 문제에서 말처럼 이동하는 부분이 추가되었다고 생각하면 됩니다. 즉, 각 위치에서 상하좌우(4방향) + 말(8방향) 이렇게 12가지 방향으로 탐색을 진행하면 됩니다.문제는 중복된 정점을 다시 방문하지 않도록 처리하는 것입니다. 처음에 제가 실수했던 점은 discovered[row][col][말로 방문한 경우 or 원숭이로 방문한 경우] 로 중복된 정점을 처리했었는데 이것의 반례로 아래의 예가 있습니다. 15 50 1 1 0 10 0 1 0 10 0 0 1 10 1 0 1 01 1 0 1 0 정답 : 6 말의 움직임에 의해 (2,1)에 위치..

BOJ#1263 시간 관리 * 문제https://www.acmicpc.net/problem/1263 * 풀이일상 생활에서 흔히 하는 고민을 다룬 문제인 것 같습니다. 😅(내일 무슨 무슨 일을 언제까지 해야 되니까, 몇시쯤 집에서 나가면 되겠구나! ) 첫째 줄에 일의 개수 N,그 다음 N개의 줄에 T와 S가 주어집니다. ( T : 필요한 시간, S : 납기 ) 일단 S 기준으로 오름차순 정렬을 합니다. 내림차순으로 해도 상관없습니다. 3 58 141 165 20 0시 부터 일을 시작할 수 있으므로가장 마지막 일(4번째 일)을 끝내기 위해서는 15시에는 일을 시작해야 합니다. 그리고 이것은 3번째 일에 영향을 주게 됩니다. 3 58 141 16 155 20 이어서 3번째 일을 끝내기 위해서는 14시에는 일을..

BOJ#10875 뱀 * 문제https://www.acmicpc.net/problem/10875 * 풀이 ※ 문제 풀 때 주의할 점 주어진 입력의 크기를 잘 살펴봅시다. L 7 TestCase #2332 L4 L4 R => 6 TestCase #3332 R1 R10 R = 9 TestCase #4332 R10 L4 R = 6 TestCase #5332 L10 L4 R = 6 TestCase #63310 L4 L4 R = 4 TestCase #7332 L4 L4 R = 6 TestCase #8342 L2 L1 L5 R = 7 TestCase #9342 R2 R1 R5 L = 7 TestCase #10352 R3 L1 L2 L10 L = 9 TestCase #11352 R3 R1 R2 R10 L = 9 Te..

BOJ#13911 집 구하기 * 문제https://www.acmicpc.net/problem/13911 University > 서강대학교 > 제 12회 총장배 서강대학교 프로그래밍 대회 Master F번 * 풀이매우 매우 추천하는 문제입니다. - 처음 생각한 알고리즘 1. 맥도날드 지점별로 다익스트라2. 스타벅스 지점별로 다익스트라3. 조건 만족하는 것 찾아내기 문제를 본격적으로 풀어보려는데,, 뭔가 찜찜합니다.입력값 범위가 심상치 않아 문제를 풀기전에 시간복잡도를 계산해봅니다. V ≤ 10,000, E ≤ 300,000 맥도날드 다익스트라 (V-2)번 : O(E*log(V)) * V-2번스타벅스 다익스트라 (V-2)번 : O(E*log(V)) * V-2번조건 만족하는 것 찾아내기 : ?? 결론 : 시간..

BOJ#1938 통나무 옮기기 * 문제https://www.acmicpc.net/problem/1938 * 풀이통나무의 길이가 항상 3이므로, 중심 위치만을 가지고 탐색을 해봅시다.상하좌우, 회전 5가지 경우의 bfs 탐색을 진행하면 되겠습니다. 정점 중복 방문 처리는 discovered[행][열][통나무 방향(세로 또는 가로)]으로 잡아봤습니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/ca62ee46326ab3ef50a46f562b4783773e0e0551/BOJ%231938_MovingLogs/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..

BOJ#2665 미로 만들기 * 문제https://www.acmicpc.net/problem/2665Olympiad > 한국정보올림피아드 > KOI 1997 > 고등부 2번 * 풀이쉬운 문제입니다. 20년 묵은 문제네요, 😅 왜 쉽냐면,검은 방을 흰색 방으로 바꾸는 개수의 제한도 없고, 바꿀 때 필요한 규칙도 없기 때문입니다. 그냥 이 문제는.. 다익스트라 돌리면 됩니다. 비슷한 문제 : 1261번 - 알고스팟 https://www.acmicpc.net/problem/12612206번 - 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 * 나의 코드 https://github.com/stack07142/BOJ/blob/431a2fe10059904f604d38bc137..

BOJ#1194 달이 차오른다, 가자. * 문제https://www.acmicpc.net/problem/1194 * 풀이bfs 탐색 문제입니다.같은 정점을 여러번 방문해야 하는데, 어떻게 방문 여부를 처리할 것인가를 생각해야 합니다. (처리하지 않으면 큐 폭발) 저는 아래와 같이 discovered 배열을 boolean[row][col][열쇠]로 구성하였습니다. 즉, 해당 위치 (row, col)에 동일한 key를 갖고 방문한 적이 있으면 다시 방문할 필요가 없다는 것입니다. key는 a부터 f까지 6개가 있으므로 비트마스크를 이용하면 6bit로 가지고 갖고 있는 key의 정보를 표현할 수 있습니다.(배열 사이즈는 여유있게 설정했습니다.) static boolean[][][] discovered = ne..

BOJ#5427 불 * 문제https://www.acmicpc.net/problem/5427 * 풀이큐를 2개 만든 후 불의 위치와 상근이의 위치를 큐에 각각 삽입합니다.step 하나당 불과 상근이가 한 level만 bfs 탐색할 수 있도록 구성합니다. 결과적으로 상근이가 탈출한 경우 step을 출력하고, 아닌 경우 IMPOSSIBLE을 출력합니다. - 비슷한 문제 : 3055번 탈출 http://stack07142.tistory.com/search/탈출 탈출과 비슷한 문제입니다. 탈출의 경우에는 입력값의 경우가 적어서 map을 3차원 배열(row, col, 시간)으로 만들었지만이 문제의 경우에는 입력값이 크기 때문에 맵은 2차원 배열로 유지하였습니다. 211 1@3 3.#.#@#.#.3 3....@....