쿠쿠의 개발일지

[문제] 출처 - https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net [문제 풀이] 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수 들이 있다. 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하면 된다. 자연수가 주어지고 연속된이라는 점에서 투포인터를 사용 할 수 있다. N이라는 자연수가 주어졌을때 N보다 작거나 같은 소수들을 리스트에 담아야 한다. 에라토스테네스의 체 사용 투포인터를 움직일때 리스트의 범위를 잘 지켜야 한다! [소스 코드] import java.io.*; import java.util.*; publi..

[문제] -출처 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N 해당 풀이 연속된 수들의 부분합 중에 그 합이 S 이상 되는 것중 가장 짧은 것의 길이를 구하는 문제이다. 연속된 수이고 자연수로 이루어져있으니 투 포인터를 이용하여 쉽게 해결 할 수 있는 문제이다. 두가지 조건만 잘 지키면 된다. 합이 S 이상 가장 짧은 것의 길이 import jav..

[문제] 출처 - https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net [문제 풀이] 위에부터 아래로 내려가면서 값을 더하며 최하단층에서 가장 최댓값을 구한다고 생각을 한다. 이 아이디어를 토대로 점화식을 d[i][j] = (i,j) 에 도착했을 때 합의 최댓값이라고 설정한다. 어떤 수가 선택되기 전에 선택된 수는 대각선 왼쪽 위, 오른쪽 위에 있는 것 즉 ( i , j )가 선택되기 전에 선택된 수는 왼쪽 위 ( i-1, j-1) 오른쪽 위 ( i-1, j )이고 D[i][j] = Max(D[i-1][j] , D[i-1..

[문제] 출처 - https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net [문제 풀이] 최댓값을 찾는 문제이므로. 입력으로 받은 단어의 자릿수를 만들고 각 단어의 합을 구하여 높은 값부터 대입해준다. EX) ABC + DEF = 100A + 10B + 1C + 100D+ 10E + 1F = 100A + 100D + 10B + 10E + 1C + 1F => 100A + 100D + 10B + 10E + 1C + 1F => A = 9 , D = 8 ..

[문제] 출처 - https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net [문제 풀이] 왼쪽 아래 꼭짓점 x1, y1 오른쪽 위 꼭짓점의 x2, y2 좌표값을 for문으로 직사각형 배열의 값을 1로 만든다. 값이 0인 지점에서 DFS를 하여 새로운 영역 개수를 저장할 ArrayList와 그 영역의 크기를 저장할 Count 값 선언 M과N 으로 주어졌지만 NM으로 하는 게 편해서 NM으로 설정하였습니다. [소스 코드] import j..

[문제] 출처 - https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [문제 풀이] DP를 사용해서 풀 수 있지만 N 조건이 15 이하라 사용하여 해결할 수 있다. 해당 날에 일을 할 수 있다/없다 라는 조건으로 계산한다. 최대 2^15 = 32768 이기 때문에 가능하다. 1. 정답을 찾은 경우 // 2. 불가능한 경우 // 3. 다음 경우 세 가지를 구현하여 문제를 풀 것이다. 아래 소스 코드와 주석을 참고하면 된다. [소스 코드] import java.io.*; import java.util.*; public class Main { static int t[]; static int..

[문제] 출처 - https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net N극(0) S극(1) 중을 하나를 나타내는 4개의 톱니바퀴를 회전시켜야 한다. 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 서로의 극이 같은 경우에는 회전시키지 않고, 다른 경우에만 회전을 시킨다. 극을 비교할 때에는 2번 6번 방향을 기준으로 한다. [문제 풀이] 시뮬레이션은 문제의 조건을 잘 읽고 그대로 이행을 해줘야 ..

문제 출처 - https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 N제한이 8이라는 매우 작은 수 3개의 벽을 세우는 모든 경우의 수를 만드는 DFS 벽을 만들고 바이러스를 퍼트리는 과정의 BFS -> 인접한 다른 정점으로 갈때 가중치가 1 *주의!! = 원본 배열을 바꾸면 안되기 때문에 복사된 배열을 사용해야 하는데 a = b 와 같은 대입연산자를 사용하면 얕은 복사가 생겨 원본 배열 값에 영향을 미치기 때문에 깊은복사를 해야한다. 문제를에 벽의개..

[문제] https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net [문제 풀이] 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하기. 주의해야 할 점은 음수를 제외한 연속합이 최대이지 않을까라고 생각을 할 수 있는데 음수를 포함해도 연속합이 커지는 경우가 있다. ex) 3 -1 3 최대합 : 5 문제를 참고하여 D[i] = i 번째 수로 끝나는 가장 큰 연속합이라는 점화식을 세울 수 있다. A[i] A[i-1] A[i] A[i-2] A[i-1..