[백준 2635]
https://www.acmicpc.net/problem/2635
입력받은 값에서 적합한 임의의 두번째 값을 찾아 이후의 값의 차를 수열로 만들어 최대 개수가 많은 수열을 찾는 문제이다.
두번째 값은 첫번째 값보다 작거나 같아야 한다.
위 문제는 사실상 두번째 값을 찾는 문제이다.
두번째 값을 찾기 위해서는 반복문을 돌며 번거롭지만 가장 적합한 값을 찾아야 한다고 생각했다.
리스트를 두개를 생성하여 루프를 돌며 다른 리스트에 저장한 수열과 비교하여 리스트를 업데이트 해 나가는 방식으로 문제를 해결하였다.
우선 입력과 리스트 생성을 위한 객체를 생성한 후 사용자의 입력을 받도록 하였다.
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> saveList = new ArrayList<>();
int cn = sc.nextInt();
sc.nextLine(); 입력을 받은 후에는 해당 값보다 작거나 같은 수를 하나씩 대입하며 두번째 값을 찾아야 한다.
루프를 돌며 해당 요소의 수열을 리스트에 저장하고 수열의 크기를 비교하여 조건에 부합한다면 리스트를 업데이트한다.
for(int i = 1; i <= cn; i++) {
ArrayList<Integer> compareList = new ArrayList<>();
compareList.add(cn);
compareList.add(i);
while(true) {
int size = compareList.size();
int number = compareList.get(size - 2) - compareList.get(size - 1);
if(number < 0) {
break;
}
compareList.add(number);
}
if(compareList.size() > saveList.size()) {
saveList = compareList;
}
}루프를 전부 순회하였다면 리스트에는 최종적으로 크기가 가장 큰 수열의 값이 저장되어 있을 것이다.
정답을 출력하기 위한 코드는 아래와 같다.
System.out.println(saveList.size());
for(int i = 0; i < saveList.size(); i++) {
int temp = saveList.get(i);
System.out.print(temp);
System.out.print(" ");
}
}
}해당 코드를 통해 첫번째 줄에는 수열의 크기가, 두번째 줄에는 수열의 값을 띄어쓰기 기준으로 하나씩 출력할 수 있다.
[코드전문]
import java.util.Scanner;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> saveList = new ArrayList<>();
int cn = sc.nextInt();
sc.nextLine();
for(int i = 1; i <= cn; i++) {
ArrayList<Integer> compareList = new ArrayList<>();
compareList.add(cn);
compareList.add(i);
while(true) {
int size = compareList.size();
int number = compareList.get(size - 2) - compareList.get(size - 1);
if(number < 0) {
break;
}
compareList.add(number);
}
if(compareList.size() > saveList.size()) {
saveList = compareList;
}
}
System.out.println(saveList.size());
for(int i = 0; i < saveList.size(); i++) {
int temp = saveList.get(i);
System.out.print(temp);
System.out.print(" ");
}
}
}해당 코드를 통해 문제를 해결할 수 있었다!
해당 문제는 어렵지 않게 해결할 수 있었다.
하지만!
내 어려움은 다른곳에 있었으니
알고리즘 문제는 문제를 정확하게 이해하는게 중요한 것 같다.
처음에 지문을 읽었을 때는 문제에서 요구하는 사항이 무엇인지 인지하지 못했는데 두세번 읽었을 때 겨우 이해할 수 있었다.
사실 이해 못해서 AI의 힘을 빌렸었다.
문제를 빠르게 읽는 것도 물론 중요하지만 정확하게 이해하는 마음가짐을 가지도록 노력하자~
