6-6화이탱

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 2의 곱셈부터 해서 소수가 아닌 수를 체크해두어 판단한다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.S..

https://www.acmicpc.net/problem/15711 15711번: 환상의 짝꿍 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이 www.acmicpc.net 에라토스테네스의 체를 사용하여 풀 수 있다! 2를 제외한 모든 홀수가 소수이다. 1) 두 수의 합이 4보다 작으면 무조건 소수 2개로 나누지 못함! 2) 두 수의 합이 짝수이면 모두 가능 3) 두 수의 합이 홀수이면 두 수의 합의 값 4 * 1012 의 루트값 2000000까지의 소수값을 확인하여 판단한다. import java.io.BufferedReader; import java.io.Buffer..

https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 1) 각 간격의 최대공약수를 찾는다! 2) 총 거리에서 최대공약수로 계산했을때 총 몇개의 가로수가 들어가는지 계산하고 현재 있는 가로수의 수를 뺀다 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java...

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net DFS로 풀었다가 시간 초과가 발생해서 BFS로 다시 풀이한 문제였다! BFS는 덜 익숙하다는게 너무나도 느껴졌다... 1)객체를 만들어서 x,y,벽 사용여부, 현재까지의 거리값 을 속성값으로 갖는다. 2) int형의 2차원 배열 check로 벽 사용여부를 넣는다. 이때, 벽 사용여부를 넣는 이유는! 만일 x,y가 벽이 아닌 곳인데 벽을 사용한 상태로 이미 통과된 적이 있..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 1) 사각형 부분은 1로 세팅한다. 2) 포문을 돌면서 0인 곳에서 count를 초기화하고 dfs를 한다! 이때, count는 넓이 계산에 사용된다. 3) dfs를 돌면서 count+1를 한다. 4) arrlist에 count를 넣는다. 5) arrlist의 개수는 영역의 개수가 되고, 값은 영역의 넓이가 된다. import java.io.BufferedReader; impor..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 가장 처음 도시에서는 무조건 주유를 해야한다는 점, 그 이후로는 가장 싼 곳에서 주유를 해서 가면 된다~ + int로는 범위가 넘기 때문에 long으로 해줘야 한다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWr..

https://www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 실버2 레벨에 맞지 않게.. 아주 간단하게 구간을 확인하여 풀 수 있는 문제였다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamW..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 생각보다 많이 헤맨 문제였다... n/2의 선수로 나누는 것으로 모든 선수는 스타트팀과 링크팀으로 무조건 들어간다!! 재귀함수를 통해서 count를 증가시키면서 방문한 곳은 스타트 팀 소속, 방문하지 않은 곳은 링크 팀 소속으로 배정하여 계산한다!! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; im..

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 계속 시간초과가 나서 힘들었던 문제였다... 결국 구글에 검색을 해봤는데 1) ListIterator iter = origin.listIterator(); 을 써서 커서를 나타내야한다. 2) BufferedWriter로 출력해야한다. - System.out vs BufferedWriter vs StringBuilder 속도 차이 숫자 1000개 출력 * 10번 ( 단위 : ns ) System.ou..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net Math.pow로 하면 시간초과가 발생한다... 분할 정복을 이용하여 문제를 해결할 수 있다! 예를 들어, 다섯제곱수이면 5 -> 2 *2 *1 ->1*1*1*1*1 이다! 네제곱수이면 4->2*2->1*1*1*1이다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public cla..