문제풀이14 [백준] 18111번 마인크래프트 - JAVA https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 구현 문제다. 가장 높은 높이부터 0까지 위에서 아래로 차례대로 계산해주는 함수를 호출하며 내려갔다. 로직은 간단한데 구현이 오래 걸린다. 채울 때는 시간을 1초 추가해주는 것도 있지만, 박스가 충분한지 확인해줘야 한다. 출력은 가장 높은 높이의 값을 출력해줘야 해서 우선순위 큐를 사용했다. 코드 import java.io.*; import java.math.BigInteger; // subtr.. 2022. 6. 12. [백준] 15686번 치킨배달 - JAVA https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 구현 문제를 풀다 보면 삼성 기출을 자주 만난다. 해당 문제도 삼성 sw 역량테스트 기출문제다. 2차원이 나오면 bfs dfs를 의심하게 된다. 하지만 문제를 읽어보면 거리 계산은 단순 수식으로 할 수 있고 백트래킹 문제인 것을 알 수 있다. 주어진 M이 치킨집의 개수이니 치킨집을 조합으로 선택해서 치킨 거리 MIN을 구해주면 끝이다. 처음 문제를 풀 때 M을 못 보고 1~N.. 2022. 6. 11. [백준] 1326번 폴짝폴짝 - JAVA https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 1차원 BFS 활용 문제다. 주의할 점은 앞도 확인해줘야 한다는 점, 방문하면 최소이므로 방문한 곳을 방문처리해줘야 한다는 점이다. 방문처리를 하지않고 풀었다가 메모리 초과가 생겼다. idx를 이용해서 해당 위치의 배수 값을 찾고배수 값으로 방문하지 않았다면 방문처리해주고 큐에 넣어주면 풀 수 있다. 앞과 뒤를 둘다 확인하는 점에 주의하자. 코드 import java.io.*; imp.. 2022. 6. 9. [백준] 1699번 제곱수의 합 - JAVA https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 다이내믹 프로그래밍을 이용한 문제다. 1, 4, 9, 16.. 과 같은 제곱수를 활용하여 주어진 수 N을 최소한의 개수로 구성하는 것이 답이다. 최적의 값을 idx에 기억해두는 바텀업 방식으로 이중 for문을 사용했다. 해당 문제에서 최적의 값은 최소한의 연산 횟수다. DP 테이블 초기화 먼저 dp 테이블을 idx는 숫자, value는 최소 연산 횟수로 사용.. 2022. 6. 8. [백준] 2206번 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 처음 시도 때 시간 초과로 풀지 못한 문제다. 모든 벽을 큐에 넣고 해당 부분을 0으로 만들었다가 bfs가 종료되면 다시 1로 만드는 식으로 과정을 진행시켰는데 시간초과가 걸렸다. 생각을 해보면 BFS는 최단 경로를 찾을 수 있고, Node class를 만들어서 BFS를 하면 해당 Node가 가장 먼저 도착한 Node일 테니 벽을 뚫은적이 있는지, 없는지에 대한 상태를 저.. 2022. 6. 1. [백준] 14501번 퇴사 (JAVA) https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제를 풀고 나서 다른 사람들의 풀이를 보니 뒤에서부터 생각해서 푸는 경우도 있던데 막상 시험장이라면 생각해내지 못할 가능성이 많아 보인다. 하던데로 앞에서 푸는 방식으로 해결하는 게 연습하기는 좋을 것 같다. 여태까지 풀어왔던 DP방식은 INDEX를 현재 시점으로 두고 이전에 구해논 DP 값으로 비교해서 구하는 경우가 많은데 이 문제는 특이하게 구한 수익을 다음 INDEX+N 방식으로 넘겨주면서 풀어야 해서 생각하기 쉽지 않았던 것 같다. 그리고 주의할 점은 미래 수익을 정의하기 이전에 현재 시점의 DP 값이 이전 - 1의 DP 값.. 2022. 4. 21. 이전 1 2 3 다음