개발왕 찌 (۶•̀ᴗ•́)۶

DFS 문제 요약 2차원 배열에서 가장 긴 등산로 만들기 규칙 가장 높은 봉우리에서 시작 4방 탐색 높은곳에서 낮은곳으로만 이동 가능 (같은 곳X) 딱 한번 최대 K만큼 높이를 깎을 수 있음 풀이 최대지점(봉우리)부터 dfs 직전 높이보다 낮으면 dfs, 같거나 높으면 높이를 깎은적이 없는 경우에만 최대 K만큼 깎아서 이동할 수 있는지 확인해서 dfs 비고 풀이 자체는 금방 떠올랐으나 예외 잡는 데에 오래 걸림 ㅠㅠ 더보기 package s01.SWEA_1949_등산로조성; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int ..

날짜 분류 번호 알고리즘 분류 링크 21-03-13 프로그래머스 12987 그리디 programmers.co.kr/learn/courses/30/lessons/12987 문제 요약 A팀 N명과 B팀 N명이 각각 무작위로 자연수를 부여받았을 때, B팀의 최대 승점 구하기 게임 규칙 A팀 한명과 B팀 한명이 서로 수를 비교하여 큰 수를 가진 팀에 +1점, 동일할 경우 둘 다 0점 모든 사람은 한번만 출전 가능하며, 서로 동일한 숫자를 가질 수 있음 B팀은 A팀의 출전 순서를 앎 풀이 A팀과 B팀을 카드 숫자에 따라 오름차순 정렬 A팀을 기준으로 반복문을 돌리면서 현재 A팀 출전 숫자보다 큰 숫자를 가진 B팀의 팀원이 나올 때까지 b의 인덱스를 증가 비고 레벨 3인데 너무 허무하게 풀려서 당황 ㅎ 더보기 pa..

날짜 분류 번호 알고리즘 분류 링크 21-01-19 BOJ 20366 이분탐색 www.acmicpc.net/problem/20366 문제 요약 N개의 눈덩이 중 4개를 골라 눈두덩이 2개로 만들어진 눈사람 2쌍을 만든다. 이중 두 눈사람의 키 차이가 최소가 되는 값 구하기 눈덩이의 키 = 지름 풀이 눈덩이의 키 순서로 정렬 정렬된 상태에서 a, b, c, d 순차적으로 골랐다고 가정했을 때 a+d와 b+c의 차이가 abcd로 만들수 있는 눈사람의 키 차이임 a, b, d를 3중 for문으로 돌리고(ㅌㅋㅋㅋ ㅠㅠ ) 나머지 c를 b+1과 d-1 사이에서 c의 값 찾기... lower bound로 c의 값 구함 c-1의 값도 고려함 (c-1와 a, b, d가 다를 경우에만) 비고 N이 600인데 시간 제한이..

날짜 분류 번호 알고리즘 분류 링크 21-01-20 BOJ 2585 이분탐색&bfs www.acmicpc.net/problem/2585 문제 요약 (0, 0)에서 (10000, 10000)까지 이동할 수 있는 최저의 연료통 용량 구하기 단, 중간에 주유를 할 수 있는 횟수는 K번 이하여야 함 참고사항 연료의 단위는 1L이며 1L당 10km 비행 가능 두 지점의 거리는 평면상의 거리임 풀이 (0, 0)에서 (10000, 10000)까지 필요한 연료량을 r(최대값)으로 두고 이분탐색 진행 mid로 목적지까지 도착할 수 있는지 없는지를 확인 bfs 사용 que에서 좌표를 하나 꺼내고 주어진 연료량으로 목적지까지 갈 수 있으면 true 반환 목적지까지 갈 수 없는데 연료횟수가 K번이면 다음 좌표로 넘어감 목적지..

날짜 분류 번호 알고리즘 분류 링크 21-01-18 BOJ 17940 다익스트라 www.acmicpc.net/problem/17940 문제 요약 환승 횟수를 최소로 하는 경로 중 소요시간이 가장 짧은 경로 찾기 지하철은 2개의 회사에서 운영하고 있으며, 운영하는 회사가 바뀔 때마다 환승 1회로 계산 풀이 다익스트라 지하철역 번호, 환승횟수, 누적 비용을 포함하는 객체를 만들어서 환승횟수와 비용을 가지고 PQ에 정렬 비고 PQ를 사용한 다익스트라로 간단하게 풀 수 있는 문제 더보기 package b17.BOJ_17940_지하철; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; imp..

날짜 분류 번호 알고리즘 분류 21-01-17 BOJ 20437 슬라이딩 윈도우 링크 문제 요약 주어진 문자열에서 어떤 문자를 정확히 K개만 포함하는 sub 문자열 중 최단 길이와 최장 길이를 구함 풀이 26개의 리스트를 만들어서 각 문자에 해당하는 문자들의 위치를 저장 각 문자별로 x번째 문자와 x+n-1번째 문자의 길이를 계산하여 최대값과 최소값을 비교 비고 가볍게 풀기 좋은 문제 더보기 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) th..

문제 요약 x 축에 사대가 있고 (a,b)에 동물이 존재함 사대로부터 거리가 L 이하인 동물만 잡을 수 있다고 가정했을 때 잡을 수 있는 동물의 수 찾기 사대의 위치 x와 동물의 위치 (a, b) 간의 거리는 |x-a| + b 풀이 동물들의 위치를 기준으로 반복문으로 돌림 해당 동물을 잡을 수 있는 사대는 y좌표 - (L-x좌표)부터 y좌표 + (L-x좌표) 사대의 위치를 정렬하여 min 값보다 크거나 같은 사대의 idx를 구함 (lowerbound) 해당 idx의 사대 위치가 min 이상 max 이하일 경우 정답에서 1 증가 또 또 또 블로그 글을 보고 힌트를 얻은,,, ㅠㅠ 어차피 min의 값보다 같거나 큰 gun의 위치를 찾는 건데 if (gun[idx] = min && gun[idx] 0 ? mi..

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); System.out.println(solution(x)); } static String solution(int x) { int height = 1; int sum = 1; while(sum < x) { height++; sum += height; } int i = x - (sum - height); int j = height - i + 1; if(height%2 == 0) return i+"/"+j; else return j+"/"+i; } } 머리로만 생각..

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); System.out.println(solution(x)); } static int solution(int x) { int result = 1; int range = 1; while(range < x) { range += 6*result; result++; } return result; } }

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); System.out.println(solution(x)); } static int solution(int x) { int result = -1; int s = x/5; while(s > 0) { if((x-s*5)%3 == 0) return s + (x-s*5)/3; s--; } if(x%3 == 0) return x/3; return result; } }