soo 문제집 완전탐색 easy 문제 52문제중 20문제를 풀었고, 그중 힌트를 참고한 문제 9개를 정리해서 학습 및 체득하려는 목적으로 작성했습니다.
| 문제 번호 | 제목 | 난이도 |
|---|---|---|
| 4690 | 완전 세제곱 | 브론즈 3 |
| 20410 | 추첨상 사수 대작전! (Easy) | 브론즈 3 |
| 2858 | 기숙사 바닥 | 브론즈 2 |
| 2966 | 찍기 | 브론즈 2 |
| 2160 | 그림 비교 | 브론즈 1 |
| 10448 | 유레카 이론 | 브론즈 1 |
| 18512 | 점프 점프 | 브론즈 1 |
| 17127 | 벚꽃이 정보섬에 피어난 이유 | 실버 5 |
| 2851 | 슈퍼 마리오 | 브론즈 1 |
4690 완전 세제곱
해결코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 2; i <= 100; i++) {
for (int j = 2; j <= 100; j++) {
for (int k = j+1; k <= 100; k++) {
for (int l = k+1; l <= 100; l++) {
if(Math.pow(i, 3) == Math.pow(j,3) + Math.pow(k,3) + Math.pow(l,3)){
bw.write("Cube = " + i +", Triple = ("+ j +","+k+","+l+")\n");
}
}
}
}
}
br.close();
bw.close();
}
}
고민의 시간과 해결방법:
- 입력값이 없다. 그냥 순회로만 풀 수 있는 쉬운 문제다.
- 1보다 큰 자연수를 찾으라 했으니 2부터 시작해서 최대 100까지니까 100까지 순회한다
- b,c,d쌍은 커지는 순이라고 했으니까 c는 b의 +1, d는 c의 +1한 값부터 시작해서 주어진 공식을 만족하는 경우, 주어진 형식대로 출력한다.
학습정리
- 깡으로 푸는 완전탐색 문제를 마주쳐서 당황해서 그런지 잘 구현되지 않았다.
- 특히 수학 공식에 대한 내용이 나와서 이것을 이해하는데 시간을 많이 드렸고 결국 힌트를 참고하지 않았나 싶다
- 수학공식 문제는 이후로도 계속 나오는데 완벽한 이해보다는 그것을 활용해서 구현하는 것에 더 중점을 두자!
- 그리고 이렇게 다중 포문은 꼭 입력값을 보고 하는 습관을 갖자.
- 만약 입력값이 커서 시간초과가 발생할 위험이 있다면, 다른 방법을 모색해야한다
문제 링크:
20410 추첨상 사수 대작전! (Easy)
해결코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int seed = Integer.parseInt(st.nextToken());
int x1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
if(x1 == (i*seed + j)%m && x2 == (i*x1 + j)%m){
bw.write(i + " " + j);
br.close();
bw.close();
return;
}
}
}
br.close();
bw.close();
}
}고민의 시간과 해결방법:
- 이 문제도 위 문제와 같다. 구하려는 a와 c를 i와 j로 두고, 두 공식을 만족하는 수를 찾을때까지 반복문을 돌리면된다
- 수학에서는 이를 연립해서 풀어야하지만 코딩에서는 정말 쉽게 반복문을 돌리면 된다!
- 어려운 문제에서는 이런 문제는 나오지 않겠지만, 마주치게 되는 문제에서 방정식을 찾아야하고 입력값이 작다면 완전탐색을 하는 것에 대해 고민해보자
문제 링크:
2858 기숙사 바닥
해결코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= r; j++) {
if((j-2)*2 + i*2 == r && (i-2) * (j-2) == b){
bw.write(j +" " + i);
br.close();
bw.close();
return;
}
}
}
br.close();
bw.close();
}
}
고민의 시간과 해결방법:
- 다음과 같은 규칙을 찾아서 만족하는 경우 출력하고 종료하도록 순회해서 풀었다
- 가장자리는 길이인 i는 직사각형의 길이와 같다. 위아래 두개 있으므로 *2를 해주고 높이는 위아래 두개를 빼서 j-2를 두개 곱한 것이랑 같다.
- 가장자리는 레드이므로 레드의 개수가 2번을 만족하는 i와 j인 경우를 조건으로 건다
- 이어서 안쪽은 i-2와 j-2를 곱한 넓이가 갈색 블록의 개수와 같다. 따라서 이 조건도 앞선 조건과 같이 만족하는 경우 j와 i순으로 출력하도록 한다 두 수가 다르면 L이 큰수, W가 작은 수가 된다고 했기 때문이다.
학습정리
- 도형 문제에 참 약한 것 같다. 도형문제를 마주치면 규칙을 이끌어내는데 집중하고 여러 문제를 접하면서 감을 키우자.
문제 링크:
2966 찍기
해결코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] sang = {"A","B","C"};
String[] chang = {"B","A","B","C"};
String[] hyun = {"C","C","A","A","B","B"};
int n = Integer.parseInt(br.readLine());
String[] answer = br.readLine().split("");
int[] ans = {0,0,0};
int max = 0;
for (int i = 0; i < n; i++) {
if(sang[i%3].equals(answer[i])){
ans[0]++;
}
if(chang[i%4].equals(answer[i])){
ans[1]++;
}
if(hyun[i%6].equals(answer[i])){
ans[2]++;
}
}
for (int i = 0; i < 3; i++) {
max = Math.max(max, ans[i]);
}
bw.write(max+"\n");
for (int i = 0; i < 3; i++) {
if(ans[i] == max && i==0) {
bw.write("Adrian\n");
}
if(ans[i] == max && i==1){
bw.write("Bruno\n");
}
if(ans[i] == max && i==2){
bw.write("Goran\n");
}
}
br.close();
bw.close();
}
}
고민의 시간과 해결방법:
- 각 사람에 대한 찍기 규칙을 찾아내서 미리 배열로 정의해둔다.
- 이후 각 사람이 맞춘 횟수를 ans배열에 저장하고, 순회하면서 정답 문자열과 비교해서 맞을 때마다 ans배열의 각 인덱스의 값을 증가시킨다
- 이후 가장 큰 값을 찾기 위해 ans배열을 순회해서 찾고 출력한다
- 마지막으로 max와 값이 같은 경우 i의 값에 따라 이름을 출력하면 된다.
학습 정리:
- 4번에서 고생했었다. if문으로 처리하려다가 너무 효율이 안나와서 힌트를 참고했는데, 순회하면서 max랑 같은 값이면 그 값은 max라는 간단한 풀이가 있어 채용하였다
- 앞으로 비슷한 문제가 있으면 이 문제를 떠올려서 해결하도록 해야겠다.
문제 링크:
2160 그림 비교
해결코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[][][] arr = new int[n][5][7];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 5; j++) {
String[] input = br.readLine().split("");
for (int k = 0; k < 7; k++) {
if(input[k].equals(".")){
arr[i][j][k] = 0;
}else if(input[k].equals("X")){
arr[i][j][k] = 1;
}
}
}
}
int ans = Integer.MAX_VALUE;
int a = 0;
int b = 0;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
int count = 0;
for (int k = 0; k < 5; k++) {
for (int l = 0; l < 7; l++) {
if(arr[i][k][l] != arr[j][k][l]){
count++;
}
}
}
if(count < ans){
ans = count;
a = i+1;
b = j+1;
}
}
}
bw.write(a + " " + b);
br.close();
bw.close();
}
}
고민의 시간과 해결방법:
- n(n-1)5*7의 순회를 진행해야한다. 이때 n이 최대 50이므로 시간 제한에 걸리지 않아 완전탐색으로 진행할 수 있다
- 처음에 풀었을 때는 각 주어진 5*7 배열을 String[][]배열로 처리하고 이어서 List로 각 배열들을 담은 뒤 비교 했었다
- 2번 방법도 가능하며, 이번에 다시 풀었을 때는 int[][][]로 3차원 배열로 처리해서 더 간단하게 풀었다
- 3차원 배열로 하면 타입 맞추기에 고민을 한번 해야한다. 뒤에 있는 둘의 타입은 문자고 맨 앞은 숫자인데 어떻게 해야할까?
- 그 고민은 '.'을 0으로, 'X'을 1로 바꾸는 방식으로 해결하였다
- 이후 1번의 방식대로 순회를 진행하면서 같지 두 그림이 같지 않은 부분에 대해 count해준다
- ans보다 작으면 count에 넣어주고 현재의 위치를 기억하기 위해 임시변수 a와 b에 i+1과 j+1을 넣어준다
- 완성한 i와 j를 출력하면 정답이 된다.
문제 링크:
10448 유레카 이론
해결코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int[] num = new int[45];
for (int i = 0; i < 45; i++) {
num[i] = (i+1)*(i+2)/2;
}
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
boolean isFind = false;
int k = Integer.parseInt(br.readLine());
for (int j = 0; j < 45; j++) {
for (int l = 0; l < 45; l++) {
for (int m = 0; m < 45; m++) {
if(num[j] + num[l] + num[m] == k){
isFind = true;
}
}
}
}
if(isFind){
bw.write("1\n");
}else{
bw.write("0\n");
}
}
br.close();
bw.close();
}
}
고민의 시간과 해결방법:
- 일단 주어진 Tn에 대해 미리 배열에 저장을 해놔야 한다
- k는 1000이므로 44까지만 만들어두면 되기 때문에 배열의 크기를 45로 하고 공식을 이용해 저장해둔다
- 이어서 3개의 삼각수의 합으로 입력값 k를 만족시킬 수 있는지 3중 포문을 통해 찾는다. 이러한 완전 탐색이 가능한 것은 각각 45번씩만 순회하면 되어서 454545번 순회하기 때문에 시간초과 발생 위험이 없기 때문이다
- boolean isFind를 이용해서 만약 3번에서 찾으면 true로 바꾸고 아니면 false를 유지토록하여 3중 포문 종료 후 그에 맞는 결과를 출력하도록 한다.
문제 링크:
18512 점프 점프
해결코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int p1 = Integer.parseInt(st.nextToken());
int p2 = Integer.parseInt(st.nextToken());
while(true){
if(p1 > p2){
p2 += y;
}else if(p1 < p2){
p1 += x;
}else{
bw.write(p1+"");
break;
}
if(p1 >= 10000 || p2 >= 10000){
bw.write("-1");
break;
}
}
br.close();
bw.close();
}
}
고민의 시간과 해결방법:
- 이전에 프로그래머스에서 풀었던 카카오 코테 두 큐 문제랑 비슷하다
- 한쪽이 더 크다면 작은 쪽에 주어진 x나 y만큼 더해준다
- 만약 같다면 p1이나 p2중 아무 수나 출력하고 break로 while문을 탈출한다
- 이제 무한루프를 탈출하기 위한 조건을 하나 생각하면 된다. 이 문제는 길이만큼 순회하는 것이 아니기고 x나 y를 더하는 문제이다
- 따라서 각 지점이 n^2번 이상 커졌는데도 만나는 지점이 생기지 않는 다는 것은 공통적으로 지나는 지점이 없다는 것이다
- 따라서 최대 입력값인 100의 제곱인 10000을 두 p1과 p2중 아무나 그 이상이 될 경우 -1을 출력하고 break로 탈출한다
학습정리
- 비슷한 유형의 문제라 반가웠다. 특히 무한 루프 탈출에 대한 한계치 설정 고민을 할 수 있는 문제라 좋은 문제였던 것 같다
- 비슷한 문제를 마주친다면 해당 문제를 떠올려서 문제를 해결할 수 있도록 하자
문제 링크:
17127 벚꽃이 정보섬에 피어난 이유
해결코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int ans = 0;
int a = 1;
for (int i = 0; i < n-3; i++) {
a *= arr[i];
int b = 1;
for (int j = i+1; j < n - 2; j++) {
b *= arr[j];
int c = 1;
for (int k = j+1; k < n - 1; k++) {
c*= arr[k];
int d = 1;
for (int l = k+1; l < n; l++) {
d *= arr[l];
}
ans = Math.max(ans, a+b+c+d);
}
}
}
bw.write(ans+"");
br.close();
bw.close();
}
}고민의 시간과 해결방법:
- 입력값이 너무 작아서 완전탐색으로 가능하다.
- 완전탐색까지는 알겠는데.. 범위가 주어져서 조금 순회가 까다로워졌다
- 그래서 고민한 방법은 각 순회 전에 각각의 범위를 해당하는 변수 a,b,c,d를 만들자였고, 각 순회가 시작할 때 해당하는 배열의 인덱스 값을 곱해서 저장하여, 값을 누적하여 확인하는 방법이었다.
- 이렇게 하면 범위를 확장해 나가면서 탐색이 가능해지며, 모든 경우를 다 확인할 수 있게 된다
- 마지막 4번째 포문의 순회가 끝난 후에는 0으로 초기화된 ans와 a+b+c+d값을 비교하여 더 큰 값을 ans에 넣어준다
- 순회 종료 후에 ans를 출력하면 정답이 된다.
학습 정리
- 이 문제는 그림을 그리고 풀었으면 이해에 큰 도움이 되지 않았을 까 싶다.
- 종이 활용이 어려운 상황이라... 가능하다면 갤럭시 노트를 활용해서라도 그림을 활용한 풀이를 진행해보려고 한다
- 순회별 범위 확장에 대해 이렇게 접근하면 되겠다는 아이디어를 받을 수 있는 문제였다. 앞으로 비슷한 문제에 대해 활용하는 방법도 생각해야겠다.
문제 링크:
2851 슈퍼 마리오
해결코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int[] arr = new int[10];
for (int i = 0; i < 10; i++) {
arr[i] = Integer.parseInt(br.readLine());
if(i!= 0){
arr[i] += arr[i-1];
}
}
int sum = 0;
for (int i = 0; i < 10; i++) {
if(Math.abs(100 - arr[i]) <= Math.abs(100 - sum)){
sum = arr[i];
}
}
bw.write(sum+"");
br.close();
bw.close();
}
}
고민의 시간과 해결방법:
- 누적합을 통해 해결해야하는 문제다
- 일렬로 놓인 배열을 정렬할 수도 없고, 순서대로 먹어서 누적되는 값을 통해 비교하는 문제이므로 누적합을 사용하지 않으면 풀이가 복잡해진다
- 따라서 이전값을 더하여 해당 위치에 저장한다
- sum이라는 임시변수를 만들고 다시 순회를 진행한다.
- 100-sum의 절댓값이 100-arr[i]보다 크면 sum에 arr[i]를 넣어준다
- 이때 가까운 수가 2개라면 더큰 수를 넣으라했으니 <= 비교를 조건으로 걸어 더 큰 값이 sum에 들어가도록 한다
- 완성한 sum을 출력하면 정답이 된다.
학습정리
- 아직 누적합에 대해 문제를 깊이 풀지는 않았지만 미리 체험해볼 수 있는 문제였다
- 2024 네이버 공채 코테에서도 누적합 문제가 나왔는데 만약 정렬을 할 수 없고 순서대로 확인해서 누적되는 값을 비교하는 문제라면 누적합 알고리즘을 적극적으로 활용하자
- 누적합은 추후 문제집을 통해 더 풀어볼 계획이다.
문제 링크:
Software Developer