2024. 1. 19. 08:14ㆍ백준알고리즘/수학
문제출처 : https://www.acmicpc.net/problem/1193
알고리즘 유형
알고리즘분류 : 수학
언어 : JAVA
문제
접근
- 지그재그 순서 :: 규칙성을 찾기 위해 아래와 같이 숫자를 나열해보니 대각선 라인의 묶음단위로 분수의 규칙성을 찾음
순번 | 분수 |
1 | 1/1 |
2 | 1/2 |
3 | 2/1 |
4 | 3/1 |
5 | 2/2 |
6 | 1/3 |
7 | 1/4 |
8 | 2/3 |
9 | 3/2 |
10 | 4/1 |
11 | 5/1 |
12 | 4/2 |
13 | 3/3 |
14 | 2/4 |
15 | 1/5 |
[찾은 규칙]
- 내가 말하는 묶음은 지그재그 대각선 한 줄을 의미
위의 숫자를 예를 들어 보자면 묶음단위 구성은
'순번' 1 / '순번' 2~3 / '순번' 4~6 / '순번' 7~10 / '순번' 11~15
- 한 묶음 단위(지그재그 대각선 한 줄을 의미)로 순차/역순 구조를 이룸. 예를 들어 좌측숫자가 순차로 증가한다면 우측 숫자는 역순으로 감소
- 한 묶음 단위로 이전 묶음의 좌측 숫자가 1이 아니면 +1된 숫자부터 나열됨. 좌측숫자는 역순으로 감소하고 우측숫자는 순차증가
- 이전 묶음의 좌측숫자가 1이면 1부터 순차증가하고 우측숫자는 이전 묶음 +1부터 역순 감소
코드
package org.example.question.수학;
import java.util.Scanner;
public class Q1193_재시도 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int X = sc.nextInt();
//1.최초 초기값 세팅
int idx1 = 1;
int idx2 = 1;
//2. flag변수를 제어하기위한 묶음단위의 시작인덱스를 담아둠
// 좌측/우측 인덱스를 증가/감소 시킬 기준을 세우기 위한 변수
int firstIdx2 = idx2; //우측인덱스 첫번째 값(묶음 단위가 시작하는 첫번쨰 값이 됨)
boolean idx1AddFlag = false; //true:+, false:-
for (int i = 1; i <= X; i++) {
//최종값 세팅을 위한 프로그램 종료
if(i == X){
break;
}
//묶음 단위가 새로 시작할지 여부 체크
if (idx1 == firstIdx2) {
//좌측인덱스 증가플래그가 켜져있을 경우 -> 좌측인덱스+1
if(idx1AddFlag){
idx1AddFlag = false;
idx1 += 1;
//우측인덱스 증가플래그가 켜져있을 경우 -> 우측인덱스+1
}else{
idx1AddFlag = true;
idx2 += 1;
}
firstIdx2 = idx2; //묶음단위 최초 idx2값을 세팅해둠
}
//묶음 내부에서 값을 증감시킴
else{
if(idx1AddFlag){
idx1++;
idx2--;
}else{
idx1--;
idx2++;
}
}
}
System.out.println(idx1 +"/" + idx2);
}
}
느낀점
해당 문제를 풀 때, 접근은 이랬다.
1. 수 들의 규칙성을 찾자! 2. 데이터구조를 어디다 담지? 분자분모구조의 숫자이니 2차원배열에 담자! 3. 근데 배열은 배열의 크기를 정의해두어야 하는데 어떻게 설정하지? 임의로 입력으로 주어지는 숫자만큼 크기를 선언하자!
하지만 , 해당 문제는 2차원배열에 굳이 값을 담을 필요 없이, 그냥 변수를 사용하면 되는 것이었다. 2차원 배열로 답안을 작성하니 '메모리초과'가 발생하여 결과를 변수로 변경하여 제출하니 정답이었다.
아직, 자료구조?데이터의 구조를? 어디다 적재적소에 담아서 문제를 해결해야할지 명확하게 이해하고 있지 못한 것 같다. 자료구조에 대해 따로 공부가 필요함을 느낀다. 부족한 점을 하나 배워서 뿌듯하다. 알고리즘이 무섭지 않은 그 날까지 열심히 해봐야 겠다.
'백준알고리즘 > 수학' 카테고리의 다른 글
[백준알고리즘] 1085번 직사각형에서 탈출 (0) | 2024.01.17 |
---|---|
[백준알고리즘] 10250번 ACM 호텔 (0) | 2024.01.16 |