백준 2970: 수학숙제 풀이 이 문제는 숫자가 아닌 문자로 구해야 하는 문제이다.각 줄은 최대 100글자이고, 항상 알파벳 소문자와 숫자로만 이루어져 있다. 100글자가 모두 숫자로 채워져있다면 int와 long의 범위를 훌쩍 넘어버리기 때문이다.NumberFormat 에러는 여기서 발생했을 것이다. 그럼 문자로 해결을 하면 되는데, 주의해야할 점은 000001 이 나올 경우 1로 출력해야한다.그래서 문자를 넣기 전에 숫자의 첫번째 문자가 "0"이라면,앞에나오는 0을 생략해주는 Check0 함수를 사용해줬다. Check0함수 내에서 0이 나오면 replace해주는 코드를 만들었는데계속해서 replace하면서 숫자의 길이가 실시간으로 변경되는 문제가 발생했다. static void Check0() { ..

백준 14888: 연산자 끼워넣기 풀이 사칙연산에 대한 조합을 만들어 준 뒤,해당 조합을 이요해서 사칙연산을 진행했다. 조합을 생성하지 않고 사칙연산 개수가 저장된 배열에서사용할 때마다 개수만큼 빼주는 방법으로 백트래킹을 순회한다면 시간을 절약할 수 있을 것 같다. 전체코드package CodingTest;import java.io.*;import java.util.*;public class 실버1_14888_연산자끼워넣기 { static int N, max, min; static int arr[]; static int operations[]; static int operation[]; static boolean visited[]; static int tmp[]; public static void mai..

백준 21921: 블로그 풀이 X기간동안의 합을 이용해서 문제를 풀었다.슬라이딩 윈도우와 누적합을 활용해서 문제를 해결했는데, 자꾸 틀렸다고 나와서 왜일까 고민하다가 아래 반례를 찾게 되었다.## 입력10 23 0 0 3 0 0 3 0 0 3## 정답36 기존의 코드에서는 while문 안에서 sum 값을 변경해 줄 때, max값을 이용해서 값을 변경해 주었는데while(left max) { max = sum; cnt = 1; } left++;} 이렇게 max값을 사용하게 되면 바로 직전의 값이 아니라 최댓값으로 sum을 바꾸게 되기 때문에 값이 나오지 않는다. 전체코드package CodingTest;import java.io.*;import java.util.*;public class 실버3_21..

백준 1940: 주몽 풀이 제공된 배열을 정렬해준 뒤,left와 right로 포인트 이동을 해주며 구해주면 된다.투포인터를 사용하면 O(N^2)를 O(N)만큼 효율적이다. right는 배열의 맨 뒤에서 부터 시작하고,left는 0번째 배열부터 시작해서  1️⃣ arr[left]+arr[right] 2️⃣ arr[left]+arr[right] > M 일 경우, right--3️⃣ arr[left]+arr[right] == M 일 경우, left++ right-- cnt++ 전체코드package 백준renew;import java.io.*;import java.util.*;public class 실버4_1940_주몽 { static int N, M; static int arr[]; static boolean..

https://www.acmicpc.net/problem/2512 풀이 나무자르기 랑 비슷한 이분탐색/매개변수 탐색 문제 이분탐색은 시간복잡도가 O(logN)이다.배열을 순회할 경우 O(N)이 걸리는데,이에 비하면 굉장히 효율적이라고 볼 수 있다. arr배열을 한바퀴 돌면서, 상한예산 일 경우, 상한 예산을 더해주고상한예산 > 지자체별 신청한 예산 일 경우, 지자체별 신청한 예산을 더해줬다.상한예산별 budget이 M보다 작으면,상한예산을 높여야하기 때문에 left값을 mid+1로 바꿔준다.(mid 보다 작은 값들은 볼 필요가 없기 때문.) 상한예산별 budget이 M보다 크면,상한예산을 줄여야하기 때문에 right값을 mid-1로 바꿔준다.(mid 보다 큰 값들은 볼 필요가 없기 때문.) 전체코드pa..

https://www.acmicpc.net/problem/2805 풀이 이분탐색을 잘 못하는 것 같아서 시도해본 문제.슬라이딩 윈도우처럼 left++ right--로 풀었더니 바로 시간초과가 발생했다ㅎㅎ 나무를 자르기 위해, 높이를 설정해줘야 하는데 초기 mid값은 가장 높은 나무의 절반으로 설정해준다.그리고 중간값 mid로 자른 나무가 내가 잘라야하는 나무보다 적을 경우mid값을 낮춰줘야 하는데, 낮출 때는 right 값을 mid -1로 설정해주면나머지 오른쪽 절반은 볼 필요가 없어진다.  전체코드package CodingTest;import java.io.*;import java.util.*;public class 실버2_2805_나무자르기 { static int N, M, left, right; s..

https://www.acmicpc.net/problem/2167 전체코드package 백준renew;import java.io.*;import java.util.*;public class 실버5_2167_2차원배열의합{ static int N, M; static int arr[][]; static int ans; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringBui..

https://www.acmicpc.net/problem/2839 풀이 규칙을 찾아서 풀었다.dp[12]dp[14]dp[16]dp[18]dp[20]dp[22]dp[24]dp[26]dp[28]dp[30]4444466666 12번째 idx부터 idx+=2를 5번 할때까지 4봉지이고, 이후 짝수 5개는 설탕봉지 2개가 증가한 6봉지이다. 4봉지 .. 6봉지 .. 8봉지 .. 씩 5번dp[17]dp[19]dp[21]dp[23]dp[25]dp[27]dp[29]dp[31]dp[33]dp[35]5555577777 17번째 idx부터 idx+=2를 5번 할때까지 5봉지이고, 이후 홀수 5개는 설탕보지 2개가 증가한 7봉지이다.5봉지 .. 7봉지 .. 9봉지 .. 씩 5번 dp[4] 와 dp[7]은 유일하게 3봉지/5봉..

17390번: 이건 꼭 풀어야 해! [2, 5, 1, 4, 3]을 비내림차순으로 정렬하면 [1, 2, 3, 4, 5]이다. www.acmicpc.net 풀이 완탐을 돌면 당연하게 시간초과가 날 것 같았다. 300,000 x 300,000이니 당연함 .. 그래서 투포인터로 문제를 풀려고 했는데, 자꾸 오류가 나는 것 ..~ 그리고 투포인터도 결국 시간초과가 났을 것 같다. 도움을 받아 해결한 문제 ~! 누적합으로 문제를 풀면 더 쉽게 풀 수 있었다. 누적합을 담은 sum배열에서 0부터 R까지의 합은 sum[R]이니까, sum[R]에서 sum[L]을 빼 준 다음 arr[L]을 더하면 정답 ! 전체코드 package 백준renew; import java.io.*; import java.util.*; publi..

1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 풀이 노드를 사용한 BFS로 접근해서 풀었다. 문제 자체는 쉽게 풀렸으나, 좌표 지정에 애를 먹은 문제 .. 그리고 char형에서 int형으로 바꿀 때 오류가 있었다. 해당 문제만 해결한다면 쉽게 풀 수 있는 문제 전체코드 package 백준renew; import java.io.*; import java.util.*; public class 실버3_1063_킹 { static BufferedReader br = new BufferedReader(new InputStrea..