Java/코딩테스트
-
백준 15486, 14658Java/코딩테스트 2023. 8. 2. 02:50
https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net - 이전에 퇴사 문제(14501, 퇴사1, 실버3) 를 풀었었어서 쉽게 푼 동적계획법 문제 - DP[i] 를 i번째 날부터 퇴사날까지 얻을 수 있는 최대 이익으로 생각하고 배열을 역순으로 계산해나가면 된다. - 참고로 퇴사 날부터 거슬러서 계산을 해줘서 일부러 DP배열 사이즈를 한 칸 더 선언해뒀다. - 각 상담별로 소요 기간을 보면서 퇴사전에 끝난 경우 / 퇴사 전..
-
백준 1027, 14502Java/코딩테스트 2023. 7. 30. 19:01
https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net - 기울기 계산하는 공식이 필요한 문제 - 처음에는 오른쪽 왼쪽 다 계산하게끔 만들었는데, 그럴 필요 없이 그냥 한 방향으로 쭉 탐색할 수 있었다. - 일단 이웃하는 애는 무조건 보이고, 내 쪽에서 보인다는 뜻은 반대편에서도 내 쪽이 보인다는 뜻이므로 한 방향으로 탐색할 때 양쪽을 같이 증가시켜주면 된다. 이 문제는 진짜 ... 계속 뭐가 안 되는건지 원인을 잘 못찾아서 푸는데 오래 걸렸던 문제이..
-
백준 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 ..