이 문제의 핵심은 "오른쪽과 아래쪽으로만"움직인다는 것이다 (이걸 안보고 처음 코드를 냈을 때 모든 테스트케이스를 틀려 많이 당황했었다..) i,j점을 오는 최단 경로는 i-1,j점까지의 최단경로+i,j-1까지의 최단경로가 되는 것이다. 로직 자체는 쉬우니 dp만 알면 이해가 될거라 생각한다. 우선 첫행, 첫열을 모두 1로 초기화하고 장애물이 첫행이나 첫열에 놓이면 그 밑의 경우의수를 모두 0으로 바꾼 후 2행부터 그리고 2열부터 끝까지 검사하는 방식으로 코드를 짜 제출했더니, 3~4개의 테스트케이스에서 실패하게 됐다.. 그러다, 질문게시판에서 그 이유를 찾게 되었다. 이런 코드라면 중간에 가는길이 막혔을 때 그 아래에 1로 초기화 된 값에 의해 최단 경로수가 0이 아닐 수 있다는 것이다. 사실, 장애물..
효율성 0점 코드 import java.util.Stack; class Solution { public String solution(int n, int k, String[] cmd) { String answer = ""; boolean[] isDeleted=new boolean[n]; Stack deleteStack=new Stack(); for (String command : cmd) { char c = command.charAt(0); if(c=='U'){ int count=Integer.parseInt(command.split(" ")[1]); int step=0; while (true){ if(isDeleted[--k]) continue; step++; if(step==count) break; }..
import java.util.LinkedList; import java.util.Queue; class Solution { public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) { int answer = 0; boolean[][] board=new boolean[52][52]; int startX1,startX2,startY1,startY2; int[][] dp=new int[52][52]; for (int i = 0; i < 52; i++) { for (int j = 0; j < 52; j++) { dp[i][j]=100000; } } //1. 하나의 직사각형 변 위에 있다. // 1-1 ..
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; class Solution { public int[] solution(int n, int s) { int div=s/n; if(div
import java.util.*; import java.util.stream.Collectors; import java.util.stream.Stream; class Solution { public long solution(int n, int[] works) { long answer = 0; PriorityQueue pq=new PriorityQueue(new Comparator() { @Override public int compare(Integer o1, Integer o2) { return o2-o1; } }); for (int work : works) { pq.add(work); } while(true){ if(n==0){ for (Integer integer : pq) { answer+=int..
오랜만에 또 알고리즘 문제를 풀려니 머리가 초기화 된 것 같았다.. 우선 문제는 알고력과 사고력을 길러 주어진 모든 문제를 푸는데 드는 최소 비용을 구하는 문제였다. 고를 수 있는 선택지는 1. 1의 비용으로 알고력or코딩력을 1 늘린다. 2. 풀수있는문제를 풀어 cost만큼의 비용을 지불하고 alp_rwd와 cop_rwd를 얻는다. 처음 시도했던 풀이(코드x) 처음 접근을 alp를 기준으로 가장 효율적인 문제리스트 , cop을 기준으로 가장 효율적인 문제리스트, 전체적(alp+cop)으로 가장 효율적인 리스트 이렇게 3개의 리스트를 Comparator를 이용해서 정렬하고 1.alp가 최대치를 넘긴경우 2.cop가 최대치를 넘긴경우 3.그렇지 않은 경우 이렇게 3개의 케이스로 나누고 1.의 경우 다시 c..
import java.util.*; class Solution { public int[] solution(int n, int[][] roads, int[] sources, int destination) { int[] answer = new int[sources.length]; //만약 시간초과만 나면 플루이드 와샬로 Map roadMap=new HashMap(); for(int i=1;io1.cost-o2.cost); pq.add(new Node(destination,0)); boolean[] visited=new boolean[n+1]; //dest 부터 i까지의 최소 거리 int[] distance=new int[n+1]; for(int i=1;i
50/100 (메모리 초과) class Solution { public long solution(int[] sequence) { int size= sequence.length; long[][][] dp=new long[size+1][size+1][2]; //i~i까지 dp //0: -1, 1:1 start long answer=Integer.MIN_VALUE; for(int i=0;i3칸 5칸 -> dp[j][j+i][0]=Math.max(dp[j][j+i-1][0]+dp[j+i][j+i][0],dp[j][j][0]+dp[j+1][j+i][1]); dp[j][j+i][1]=Math.max(dp[j][j+i-1][1]+dp[j+i][j+i][1],dp[j][j][1]+dp[j+1][j+i][0]); } a..
