Java
-
백준 17070, 2212, 12018, 14719Java/코딩테스트 2023. 7. 26. 17:04
백준 17070https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의www.acmicpc.net- BFS로도 풀어보고, DP로도 풀어봤다. 처음에 BFS풀 때 움직일 수 있는 모든 방향을 리스트에 저장해서 다 도는 방식으로 구현했었는데, 시간초과 났었다. - 오른쪽으로 이동 가능한 경우 : 이전이 대각선이거나 가로 방향일 때 - 아래로 이동 가능한 경우 : 이전이 대각선이거나 세로 방향일 때 - 대각선으로 이동 가능한 경우 : 이전 상태 상관없이 다 가능 ..
-
-
백준 1149, 12852, 17135Java/코딩테스트 2023. 7. 21. 09:22
https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 동적계획법 문제 - 각 색칠 비용 저장할 2차원 배열 cost - DP[ i ] [ j ] : i번째 집에 j색(0 빨 - 1 파 - 2 초) 칠했을 때 드는 최소 비용 - 이웃하는 집끼리 색 안겹치게 하는 것만 기억하면 쉬운 문제 import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt..
-
백준 20058, 프로그래머스 - 섬 연결하기, 보석쇼핑Java/코딩테스트 2023. 7. 12. 08:30
https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net * 삼성 기출문제 (시뮬레이션, 구현, 탐색) 1. 단계를 입력받고 칸을 나눈다. 참고로 이때 바로 원본배열에 적용하면 안된다. (동시에 녹이고 반영해야하므로) 2. 각 격자를 회전시키는 함수 수행 3. 얼음 녹이기 (모든 얼음은 동시에 녹아야 한다!!!! 꼭 기억할 것!) 4. 다 끝나면 덩어리 출력 이런 문제의 경우 미리 각 움직임을 dirX, dirY 배열에 정의해두면 편..
-
백준 2579, 11057 - JAVAJava/코딩테스트 2023. 7. 5. 03:52
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net (출발지점) 10 20 15 25 10 i (현재 위치) - 한번에 한칸 또는 두칸 이동이 가능하며 세칸을 연달아 올라갈수는 없다. - DP 배열은 각 칸에서 가질 수 있는 최대 점수로 잡았다. - 만약 i가 25에 있다고 가정해보자 - 이경우 DP[i-3] (표의 10) + stairs [i-1] (표의 15) 또는 DP [i-2] 이 2가지 케이스 중 선택하게 된다. - DP[i-1]을 사용하지 않는 이유..
-
백준 11048 - JavaJava/코딩테스트 2023. 6. 29. 13:58
https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 쉬운 동적계획법 문제 이동 가능한 방향이 오른쪽, 아래쪽, 대각선 오른아래. 그러므로 각 칸의 최대 사탕개수는 자신의 왼쪽, 위쪽, 대각선 왼쪽 위 중의 최댓값 + 그 칸에서 얻을 수 있는 사탕개수가 된다. 이 점화식을 바탕으로 풀어나가면 되는 문제. import java.io.*; import java.util.*; public class p11048 { public static ..
-
백준 9205 - JavaJava/코딩테스트 2023. 6. 29. 13:31
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 집 - 편의점들 - 페스티벌 장소 이렇게 각각의 장소를 posInfo에 저장. 50m에 맥주 하나씩 먹으므로 맨허튼 거리로 계산했을 때 1000까지가 최대 움직일 수 있는 거리이다. 움직일 수 있는 반경에 있는 장소들을 선으로 연결해서 그래프를 만들고, 그 그래프를 탐색했을 때 페스티벌 장소에 도착할 수 있는지에 따라 결과를 출력하면 된다. DFS 한번 쭉 돈다음에 도착지점을 방문했는지 여부..
-
프로그래머스 도둑질 - JavaJava/코딩테스트 2023. 5. 26. 19:41
https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 로직 집이 원형으로 배치되어 있다는 것이 이 문제의 함정이다. 첫 번째 집에서 훔쳤는지 안 훔쳤는지 따라 마지막 집을 훔칠 수 있는 여부가 달라지기 때문이다. 그래서 첫 번째 집 턴 경우 / 안 턴 경우 2가지 모두 DP돌리고, 그 두가지 중 max 값 찾는 것으로 로직을 짠다. 점화식 DP[i] -> i번째 집까지 방문했을 때 얻을 수 있는 최대 금액 1) 첫 번째 집을 고른 경우에는 DP[0]..