2022. 1. 29. 14:36ㆍPS (Program Solving)/BOJ (백준)
문제 설명
https://www.acmicpc.net/problem/2798
접근 방법 - 브루트포스 알고리즘을 이용한 연산 문제
백준의 2798번 문제는 브루트포스 알고리즘을 이용하여 해결해야 하는 문제이다.
브루트포스 알고리즘이란 모든 경우의 수를 감안하며 해답을 얻어내는 알고리즘을 뜻한다.
이와 관련한 다른 문제에 관해서, 이전에 필자가 작성한 글이 있다. 이 알고리즘이 아직 어색하다면 아래의 링크 글을 한번 참고해보길 바란다.
https://smary-it.tistory.com/22
브루트포스 알고리즘을 이용했기 때문에 이 문제의 코드 가독성도 떨어질 수 있다.
필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.
코드의 실행 순서
1) 카드 개수(n), 목표 수(m), n에 따른 각 카드의 숫자를 순차적으로 입력받는다.
2) 합계 변수 sum과 정답을 저장할 max 변수를 0으로 초기화하며 선언한다.
3) 3중 반복문을 실행한다.
- i, j, k 각각을 카드의 숫자라 가정하며 3중 반복문을 실행한다. (3개의 숫자가 겹치지 않게끔 설정한다.)
- sum에는 3개의 숫자를 모두 더한 값을 저장한다.
- b1과 b2를 선언한다. 여기서 b1은 m에 max를 뺀 값이며, b2는 m에 sum을 뺀 값이다.
- sum이 m보다 작거나 같으며, b2가 b1보다 작다면 max에 sum값을 저장한다.
(여기서 b2가 b1보다 작다는 건, 현재 sum의 값이 max의 값보다 m에 더 가깝다는 것을 의미한다.)
4) 모든 연산이 끝나면, 최종적으로 저장된 max를 출력하며 실행 종료한다.
성공한 코드
import java.util.Scanner;
//백준 2798번 코드
public class Main {
public static void main(String args[]) {
Scanner s=new Scanner(System.in);
//입력부분
int n=s.nextInt();//카드 개수
int m=s.nextInt();//목표 수
int a[]=new int[n];//카드에 적힌 숫자
for(int i=0;i<n;i++) {
a[i]=s.nextInt();
}
int sum=0;
int max=0;
for(int i=0;i<n-2;i++) {
for(int j=i+1;j<n-1;j++) {
for(int k=j+1;k<n;k++) {
sum=a[i]+a[j]+a[k];
int b1=m-max;
int b2=m-sum;
if(sum<=m&&b2<b1) {max=sum;}
}
}
}
System.out.println(max);
}
}
제출 결과
(2020.02.07 백준 2798번 문제 제출 결과)
'PS (Program Solving) > BOJ (백준)' 카테고리의 다른 글
[백준 BOJ] 2869번 달팽이는 올라가고 싶다 (C언어) (0) | 2022.01.29 |
---|---|
[백준 BOJ] 2864번 5와 6의 차이 (C언어) (0) | 2022.01.29 |
[백준 BOJ] 2775번 부녀회장이 될테야 (C언어) (0) | 2022.01.28 |
[백준 BOJ] 2753번 윤년 (C언어) (0) | 2022.01.28 |
[백준 BOJ] 2750번 수 정렬하기 (C언어) (0) | 2022.01.28 |