공부-코딩테스트/코테풀이 - 자바, 파이썬52 19238. 스타트 택시 (백준, 자바) 문제 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 1. 단순히 테이블 상에서 가장 가까운 손님을 찾는다. 2. 손님의 목적지까지 데려다준다. 손님을 다 태워줄때까지 반복하면 되는 문제이다. BFS를 사용해서 가까운 손님(거리가 같으면 행,열 조건에 맞게 행렬 비교)을 찾고, 목적지까지 태워주는 대신 연료량을 체크하면 되는 문제 조건은 간단하나 두가지 문제가 있어 시간이 많이 걸리게 되었다. 시간초과 손님을 목적지까지 바래다 주자마자 다음 손님이 위치해 있는 경우 .. 2022. 9. 18. 6497. 전력난 (코딩테스트, 백준, 자바) 문제 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 나의 풀이 두 집 사이에 왕래를 하려면 반드시 길을 지나야 하며 길을 지나기 위해서는 불이 켜져있어야 한다. 불이 켜진 길은 거리만큼의 비용이 든다. 모든 집이 왕래가 가능해야 하기때문에 고립되어 있는 집이 없도록 해야 한다. 모든 선에는 비용정보가 있다. -> 모두가 연결되어 고립되지 않도록 하되 선들의 비용합이 최소를 선택 집 수 -1 2022. 8. 29. 유기농 배추 (자바, 코딩테스트, 백준) https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 나의 풀이 : 재귀로 해결 테이블을 사용해서 배추의 위치를 찍는다. 그 다음 테이블을 탐색하며 배추를 찾는다면 처음 한번만 카운트를 한 다음 인접한 배추들을 모두 제거하는 remove메소드를 수행한다. 인접한 배추를 모두 뽑고 처음 한번만 카운트 한다면 문제에서 필요로 하는 답을 얻을 수 있다. 나의코드 import java.io.BufferedReader; import java.io.InputStreamRe.. 2022. 8. 9. 다리 놓기 (자바, 코딩테스트, 백준) 문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 시간초과 import java.io.BufferedReader; import java.io.InputStr.. 2022. 8. 4. 11660. 구간 합 구하기 5 (자바, 코딩테스트, 백준) 문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 검정색 부분은 0으로 채웠다고 생각하자 (편의상) 이전 문제의 구간 합 구하기 4번의 업그레이드 버전 1차원 부분합 풀이가 아닌 2차원 부분합을 고려하면 된다. 녹색 범위안의 합계를 구하기 위해서 생각해본다면 (연두색 부분은 만들어질 때 누적합으로 만들어진다고 생각) (기존에 들어갈 값) - (자신을 기준으로 위쪽값) - (자신을 기준으로 왼쪽.. 2022. 8. 3. 11659.구간 합 구하기 4 (자바, 코딩테스트, 백준) https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 나의 풀이 기존 배열값들을 누적합으로 전환하였다고 생각해보자. 7번 배열의 실제 값은 기존 배열값들에서 1~7번까지의 값들의 합이 들어갈 것이다. 이때 4번 배열부터 7번 배열까지의 값의 합을 구하고자 한다면? 7번 배열에서 3번 배열값을 빼버리면 7번 배열안에 있던 실제로 1~3번까지 값들이 배제되기 때문에 남은 값들의 합인 4~7번 배열값들의 합계가 남게된다. 나의 코드.. 2022. 8. 3. 이전 1 2 3 4 ··· 9 다음
