https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 1026번 : 보물 [수학, 그리디 알고리즘, 정렬] 이번 문제의 아이디어는 '가장 큰 수와 가장 작은 수를 곱해야 한다' 는 것이다. 문제에는 A 배열은 순서를 바꿔도 되지만 B 배열은 바꾸면 안된다고 명시해두었는데, A와 B의 곱셈을 더하는 것으로 이뤄진 이 문제에서 A 배열의 순서를 바꿀 수 있다면 B의 순서를 내버려두는 것은 큰 의미가 없다. 즉, 공식이나 순서까지 출력하라는 것이 ..
java
https://www.acmicpc.net/problem/11912 11912번: 격자 보존하기 승현이는 1 × n 크기의 격자판을 가지고 있습니다. 각 칸에는 1 이상 n 이하의 자연수 번호가 왼쪽에서부터 차례대로 붙어있습니다. 이 중 k개의 칸에는 말이 하나씩 놓여 있는데, 이 말들은 격자 www.acmicpc.net 11912번 : 격자 보존하기 [그리디 알고리즘, 정렬] 어떤 격자가 말에게 더러워지지 않는 경우는 두 가지를 생각할 수 있다. 1. 칸막이를 한 개 사용해야 하는 경우 : 시작 ~ 첫 번째 말 / 마지막 말 ~ 끝 2. 칸막이를 두 개 사용해야 하는 경우 : 말과 말 사이 따라서 해당 두 가지 경우를 따로 저장했다. int[] one = new int[2]; // 칸막이 하나만으로 보..
https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 이 역시 [소수의 연속합]에서 사용했던 에라토스테네스의 체를 복습할 겸 풀어보았다. 문제 자체에서 에라스토스테네스의 체를 잘 설명해주고 있다. 위 문제를 풀었을 때에는 소수가 아닌 값을 구할 때 while문을 통해 곱해주었지만, 이번에는 for문을 사용해보았다. 다른 사람의 코드를 봤을 때 이 편이 조금 더 깔끔해보였기 때문이다. 그를 바탕으로 작성한 에라토스테네스의 체는 다음과 같다. for (int i = 2; i
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 이전에 올렸던 [소수의 연속합]이라는 문제에서 투 포인터를 구현했을 때 if문과 break을 남발한 것이 마음에 걸려 같은 알고리즘의 문제를 풀어보았다. 골자는 똑같다. 구간합이 주어진 수 M과 같거나 큰 경우에는 start를 1 올리고, M보다 작은 경우에는 end를 1 올려 주어서 해당하는 arr의 값을 더해준다. M과 같은 경우에는 count도 1 더..
1644번 : 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제를 풀면서 필요했던 것은 1. 에라토스테네스의 체 2. 투 포인터 의 개념이었다. 1. 에라토스테네스의 체 숫자를 더하고 빼가면서 그 때마다 소수인지를 가늠하는 것은 비효율적이기 때문에, 자연수 N의 최대값인 4,000,000까지의 배열을 만들고, 각 숫자가 소수인지 먼저 찾았다. 소수란, 1과 자신 외에 약수가 없는 수를 말한다. 1) 그럼 가장 먼저 떠오르는 것은 2부터 4,000,000까지 for문을 돌리면서 자신보다 큰 수 중 자신으로 나눠지는 수가 있는지 확인하는 것이다. 하..
https://www.acmicpc.net/problem/14714 14714번: 홍삼 게임 (Easy) 첫 번째 줄에 “질서 있는 홍삼 게임”의 참가자의 수 N(2 ≤ N ≤ 500), 은하가 먼저 지목한 사람의 번호 A와 두 번째로 지목한 사람의 번호 B(1 ≤ A, B ≤ N, A ≠ B), 각 지목권의 지목 간격을 나타내 www.acmicpc.net BFS를 사용한 문제다. 일단 방문 체크를 할 수 있는 배열을 만들었다. 이름은 쉽게 map으로. 초기에 map은 (지목권 A, 지목권 B)를 체크했다. 예를 들어 3번째 지목에 2번 사람이 지목권 A를 가지고, 4번 사람이 지목권 B를 가진다면, map의 (2, 4)는 3이다. 이렇게 만든 이유는 어떠한 (A, B)의 경우가 나왔을 때, 그 이후에 ..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 골드 5 접근 방법 1 : 처음 생각 난 dfs로 풀어보았다. 파이프가 놓인 방향이 가로면 0, 대각선이면 1, 세로면 2로 방향을 정한 후, 각 방향마다 조건을 따져서 위치를 일일이 옮겨주었다. 파이프의 끝부분이 (N-1, N-1)이 될 때까지 계속 진행하도록 하였다. N의 범위가 작아서 시간 초과가 나오지는 않았지만, 21일 java 기준 1724/1801등으로 다른 ..
https://www.acmicpc.net/problem/2920 2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net solved.ac의 CLASS를 높이려고 하나씩 풀던 중 브론즈2 문제에서 틀렸다. 반례 찾는 법을 배우려는 중이라, 무조건 맞을 거라 생각했던 이 문제가 틀린 점을 적어놓으려고 한다. 처음 썼던 코드 : import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream..
