밤이 블로그

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#10814 나이순 정렬 * 문제https://www.acmicpc.net/problem/10814 * 풀이PriorityQueue를 이용해보았습니다.나이순으로 정렬하고나이가 같은 경우 입력 순서대로 출력되는 것을 보장하지 않으므로 order 변수를 하나 추가해서 해결하였습니다. (다른 풀이)정렬할 필요 없이 ArrayList의 배열을 선언하고 나이 idx에 맞게 이름을 추가해주면 됩니다. * 나의 코드https://github.com/stack07142/BOJ/blob/062e7ce8f6877dc0ca458b108ed6b2cc8c2b4fbe/BOJ%2310814_SortByAge/src/Main.java import java.io.*; import java.util.PriorityQueue; im..

BOJ#1541 잃어버린 괄호 * 문제https://www.acmicpc.net/problem/1541 * 풀이문제 풀이 과정 55-50+40-10-30-20+40 int minSum = 0; 1. 입력받은 String을 "-"를 기준으로 분리합니다. {55, 50+40, 10, 30, 20+40} 2. 첫번째 원소는 그냥 더해주고 (문제 조건에 따라 첫번째 숫자는 양수이다)minSum = 55; 3. 나머지 각각의 원소에 대하여 합을 구한 뒤 minSum에서 빼줍니다. {55, 50+40, 10, 30, 20+40}{55, 90, 10, 30, 60} minSum = 55 - 90 - 10 - 30 - 60; * 나의 코드https://github.com/stack07142/BOJ/blob/697a29..

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#14503 로봇 청소기 * 문제https://www.acmicpc.net/problem/14503 * 풀이2017년 상반기 삼성전자 SW 역량테스트 기출문제입니다.설명할 것이 없는 문제입니다. 문제 조건에 맞게 구현하시면 됩니다. * 나의 코드https://github.com/stack07142/BOJ/blob/442d75f4db250b3532123d0ae00bd92b50daef30/BOJ%2314503_RobotCleaning/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#1..

BOJ#14500 테트로미노 * 문제https://www.acmicpc.net/problem/14500 * 풀이2017년 상반기 삼성전자 SW 역량테스트 기출 문제입니다. 테트로미노에서 dfs로 탐색 가능한 블록이 있고, 탐색 불가능한 블록(ㅓ, ㅗ, ㅜ, ㅏ)이 있습니다.즉, dfs로 탐색 + (ㅓ,ㅗ,ㅜ,ㅏ)에 대해 탐색을 하면 답을 얻을 수 있습니다. (ㅓ,ㅗ,ㅜ,ㅏ) 탐색 아이디어는 다음과 같습니다. 현재 위치가 (row, col)일 때(row, col)값과 (row, col)에서 상,하,좌,우 4방향 값을 모두 더해줍니다. 그리고 4방향 값에서 최소 값을 다시 빼줍니다.= 현재 위치 값 + 4방향 sum - 4방향 값 중 최소값 즉 플러스 + 모양에서 4방향 중 가장 최소값을 빼면 (ㅓ,ㅗ,ㅜ,..

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#3190 뱀 * 문제https://www.acmicpc.net/problem/3190 * 풀이map과 direction 2차원 배열을 선언하였습니다. map이 가질 수 있는 값 : 0(빈칸), 1(뱀), 2(사과) direction이 가질 수 있는 값 : 상, 하, 좌, 우→ 각 위치(row, col)에서 머리 또는 꼬리가 어느 방향으로 이동해야 하는지 알기 위함 시뮬레이션 진행 알고리즘은 아래와 같고, 중간 중간에 map과 direction 정보를 업데이트해서 답을 찾을 수 있게 하였습니다. 머리 이동 - 맵을 벗어난 경우 - 종료 - 빈칸인 경우 - 꼬리 이동 - 사과인 경우 - None - 뱀인 경우 - 종료 ↓ 테스트 케이스 보기 (클릭) ↓5054 D8 D12 D15 D20 L 20 83..