나의개발일지

https://www.acmicpc.net/problem/1932 아래층으로 내려갈 땐 지금 당장 값이 작아도 끝까지 도착했을 때의 값이 더 클 수 있다.그럼 반대로 생각해보면 된다!위층으로 올라갈 때 직전 값 중 큰 값을 누적해가면 dp[0][0]이 최댓값이 된다.for(int i=n-1; i>=0; i--){ for(int j=0; j package BOJ.DP;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ_1932_정수삼각형 { public static void main(S..

https://www.acmicpc.net/problem/2170 처음엔 pq를 사용했는데 시간초과가 떠서 방법을 변경했다.정렬 후에는 이후 값이 무조건 직전값에 영향을 받을 수 밖에 없기에 그때그때 확장하는 방법이 가능해진다. 1. x값 오름차순 정렬 x값이 같다면, y값 오름차순 정렬2. 만약 다음 값이 이전 값에 걸친다면 끝 좌표만 확장2. 만약 걸치지 않는다면 이전 선의 길이를 계산해 저장한 후, 현재 x, y를 새로운 시작과 끝 값으로 정의3. 마지막 선 길이까지 더한 후 결과 출력 package BOJ.Greedy;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java..

https://www.acmicpc.net/problem/12852 우선 N의 범위가 최대 백만이기에, 각 3가지 경우를 모두 메모이제이션 하는 것은 불가능했다.그렇다면 최대 1차원 배열을 사용해야 한다는 것인데, 규칙이 뭘까? 하고 dp 배열을 그려봤다.예제 2를 대입해서 배열의 값으로는 연산 횟수를 저장하고자 할 때,이전 값에서 * 3, * 2, + 1 을 해서 현재 값이 되는 수의 배열 값 + 1(1회 연산) 을 한 것들 중 최솟값을 저장 하면 되겠다 싶었다.그래서 처음에 아래와 같이 작성하여 제출했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { ..

https://www.acmicpc.net/problem/2615 처음에 문제 읽고 설계했던 방식은 다음과 같다.1. 모든 바둑돌의 좌표를 구조체를 만들어 바둑돌 색상과 함께 큐에 저장한다.2. 하나씩 꺼내면서 dfs로 8방 탐색을 한다.3. 범위를 벗어나거나 방문했거나 다른 바둑돌 색상을 만나지 않고, 같은 바둑돌 색이면 cnt+1을 한다.4. 범위를 벗어나거나 방문했거나 다른 바둑돌 색상을 만나면 cnt를 확인해서 5이면 그 때의 시작 좌표를 출력한다.하지만 2-3%에서 틀렸고, 좌표를 찍어보며 수정하는 과정에서 엄청나게 많은 허점이 있음을 깨달았다. 1번 허점)그냥 큐에 저장하면 안됐다. 처음엔 위에서 아래로 배열을 탐색하기 때문에 조건을 만족한다고 생각했는데,반례를 보면서 만약 바둑돌이 왼쪽 아래..

https://www.acmicpc.net/problem/1080A 배열을 차례대로 탐색하다가 B 배열과 다른 부분에서 3x3 만큼을 뒤집는다.종료후, B 배열과 동일한지 확인한다. (0, 0)부터 (n-1, m-1)범위의 값을 모두 비교하고 뒤집었는데, 제출하니 틀렸다.무조건 3x3 배열만큼을 뒤집어야 하기에 아래와 같이 설정해야 한다.또한, 배열 크기가 3미만이지만 A 배열과 B 배열이 애초에 동일한 경우에는 0으로 결과값이 나와야 한다.for(int i=0; i 1. A 배열과 B 배열과 동일하면 0 출력2. 입력 받은 배열의 크기가 3미만이면 -1 출력3. (0, 0) 부터 (n-3, m-3) 까지 탐색하며 B 배열과 다른 값을 찾으면 A배열의 해당 위치부터 3X3 만큼 뒤집는다. 4. A배열과 ..

https://www.acmicpc.net/problem/1138 처음엔 순서대로 주어진 위치만큼 앞에 자리를 남겨두고 저장하고, 기존 수와 비교하며 뒤로 밀고 넣으면 되겠다하고 구현 했다.하지만 그렇게 하니 예제 4에서 결과값이 6 2 3 4 5 7 1 이 나왔다.작은 키부터 넣으면 앞에 큰 키의 개수를 제대로 고려하지 못하는 것이었다. 그래서 큰 키부터 넣어야 된다는 것을 깨달았다.1. 큰 키서부터 주어진 위치만큼 앞에 남겨두고 위치시킨다.2. 만약 해당 자리에 값이 이미 들어있다면 해당 값은 무조건 더 큰 값이 있을 것이므로 뒤로 쭉 밀고, 지금 값을 자리에 위치시킨다.3. 그렇게 위치시킨 값을 출력하면 끝! package BOJ.Greedy;import java.io.BufferedReader;i..

https://www.acmicpc.net/problem/16953 A에서 B를 만드는 방법은 여러개이고, 현재 값에서 다음 값으로 갈때 어떤 연산을 해야 더 빠른지 알 수 없다.하지만 역순으로 생각하면 다르다! B에서 1이 있으면 무조건 1을 더하는 연산을 쓸 수 밖에 없으니 이 연산을 우선순위로 두고 나아가면 된다.즉, B -> A로 가면서 1이 있으면 1을 제외하고, 1이 없으면 2를 나누고, 두 연산 다 되지 않거나 B의 연산값이 A보다 작아지면 -1을 출력한다. package BOJ.Greedy;import java.util.Scanner;public class BOJ_16953_AtoB { public static void main(String[] args) { Scanner..

https://www.acmicpc.net/problem/19941 처음으로 그리디 문제 읽으면서 떠오른 생각왼쪽에 있는 버거부터 먹어야 사람이 먹을 수 있는 버거의 수가 최대가 된다.사람을 만났을 때 왼쪽부터 k만큼 탐색해서 버거가 있으면 먹고, 없으면 오른쪽 버거를 먹으면 된다.한번 먹은 버거는 또 먹을 수 없으니 check 배열로 먹은 버거는 체크해준다.  package BOJ.Greedy;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ_19941_햄버거분배 { static int n, k; ..

https://www.acmicpc.net/problem/1449  그리디는 항상 해결방법을 떠올리는 게 참 어려운 것 같다,,이 문제는 주어진 물이 새는 곳의 위치를 정렬 해 두고, 주어진 테이프 길이 안에 위치하는 지 확인하면 되는 문제이다.즉, 첫번째 위치에서 -0 .5를 시작지점(left)로 두고 + 테이프의 길이(l) 안에 다음 물이 새는 위치가 더 오른쪽에 위치한다면테이프의 개수를 1 카운트하고, 시작지점을 다음 물이 새는 위치 - 0.5 지점으로 변경해주면 된다.  package BOJ.Greedy;import java.util.Arrays;import java.util.Scanner;public class BOJ_1449_수리공항승 { public static void main(Str..

https://www.acmicpc.net/problem/2217 각 각의 로프의 최대 중량이 주어지고, n개의 로프를 병렬로 이용하면 물체 무게를 n빵해서 들어올릴 수 있다.주어진 예제로 생각해 보자면, 15 로프를 이용하면 최대 15까지 들 수 있지만 10 로프를 함께 이용하면 최소 중량인 10의 2배(로프가 2개니까)까지 들 수 있다.그럼 10과 15 로프를 병렬로 이용하는 게 최선이다.만약, 주어진 로프가 5와 20 이라면 20 로프 하나로 20을 들 수 있고, 5 로프를 함께 이용하면 5*2=10밖에 들지 못한다.따라서 20로프를 하나만 이용하는 게 최선이다.이를 통해, 우선 병렬보다는 최대 중량의 로프 1개를 이용할 때를 확인해보는 게 우선순위라는 것을 알 수 있고, 그 뒤로는 n빵일 때를 차..