Dogfootruler Kim

문제 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 및 소스코드 입력받은 용액의 정보들을 정렬한 후, 두개의 포인터를 사용해서 인덱스 양 끝을 가리키게 만든 후 특성값을 비교해가면 된다. 주의할 점은 알칼리성 용액의 정보만, 혹은 산성용액의 정보만 들어올 수 있기 때문에 특성값 비교 후에 음수인지 양수인지 확인 후 포인터를 옮겨줘야 한다. 그렇지 않았을 때의 반례 5 -9 -8 -7 -6 -5 정답 : ..

문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 및 소스코드 이 문제에서는 연산자가 +와 - 두개 밖에 없다. 곱하기와 나누기가 있었다면 좀 더 복잡했겠지만 (다행..) 만약 1+2+3-4+5+6 이러한 식이 있을 때 합이 최소가 되기 위해서는 - 뒤에 부분을 먼저 더한 후 뺄셈을 해주게 되면 된다. 따라서 (1+2+3)-(4+5+6) 이렇게 계산해야하므로 1. "-" 토큰을 기준으로 분리시킨다. 1+2+3 과 4+5+6 2. ..

문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 및 소스코드 회전과 대칭이 가능하면서, 깊이가 4인 dfs로 풀면 된다. ( 티스토리 안봤으면 노가다했을 듯 ㅠㅠ.....) ㅗ, ㅏ, ㅜ, ㅓ 이 모양의 경우에는 위의 방법으로 풀 수 없다. 따라서, + 인접한 네 방향을 모두 더해준 다음 인접한 네 방향에 있는 값들 중 최솟값을 빼주면 된다. import java.io.BufferedReader; import java.io.IOExc..

문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 풀이 및 소스코드 로프는 그리디 문제다. 그리디를 안푼지 너무 오래돼서 풀기로 했는데, 오랜만에 푸니까 넘 어려웠다. ㅋㅋㅋㅋㅋ 방법은 간단했다. 내림차순으로 정렬한 다음 큰수부터 차근차근 비교해나가면 된다. 로프 [10, 15, 20, 23, 40] 이 존재 할 때, 1. 내림차순으로 정렬 [40, 23, 20, 15, 10] 2. 중량 40 로프를 하나 선택 -> 중량 40 가능..

풀이 및 소스코드 아래 그림처럼 조망권을 검사할 건물의 위치를 i라고 했을 때 i를 기준으로 왼쪽 2개의 건물과 오른쪽 2개의 건물의 높이를 검사해주면 된다. 1. 하나라도 현재 검사할 건물의 높이보다 높다면 -> 더이상 보지않고 다음 건물을 검사한다. 2. 이웃한 건물들의 높이가 현재 건물의 높이보다 작다면 -> 그 중에서 가장 높은 건물을 찾고 현재 건물 높이 - 가장 높은 건물의 높이 를 해주면 조망권이 확보된 세대 수가 나온다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Solution { public s..

풀이 및 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.StringTokenizer; class Solution { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 및 소스코드 이 문제는 N이 1024이고, 부분합을 100,000번 구해야 함 그때그때 부분합을 구하게 되면 n^2(1024*1024)*m(100,000) => 시간초과 따라서 dp로 풀어야 한다. https://subbak2.tistory.com/65 [BOJ 백준] 구간 합 구하기 5(11660) Java 링크 : https://www.ac..

문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 및 소스코드 배추가 있는 곳이면 지렁이 한 마리만 카운트 해주고 연결되어있는 곳들은 bfs를 돌려 일반땅으로 만든다. (1->0) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; impor..