📜 코딩테스트/BAEKJOON\백트래킹

백준 14888번 : 연산자 끼워넣기 (JAVA) 문제 풀이

2021. 1. 11. 16:34
목차
  1. 문제 분석
  2. 전체 코드
반응형

www.acmicpc.net/problem/14888

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 

www.acmicpc.net

 


 

 


문제 분석

처음의 연산할 숫자의 개수가 주어지고, 둘째 줄에는 연산할 수, 셋째 줄에는 연산자의 개수가 주어진다.

 

예를 들어 입출력 2를 보면,

3
3 4 5
1 0 1 0

연산자는 + , x  각 1개씩 사용 가능하다.

모든 경우의 연산을 보면,

3 + 4 x 5 = 35
3 x 4 + 5 = 17

결과가 35, 17인 두가지 경우가 나온다.

 

먼저 재귀 함수 부분 코드를 살펴보자.

static void dfs(int depth, int sum) {

     /* 종료 조건 */
     if (depth == N) {
         if (MAX < sum)  MAX = sum;		// 왜 if-if 로 구현 했는가?
         if (MIN > sum)  MIN = sum;		// 만약, 결과 값이 2, 3, 4 순으로 온다면 if-else로 구현했다면, MAX 값만 변경 되면서 MIN값이 제대로 안들어 갔을 것이다.
         return;
     }

     for (int i = 0; i < N - 1; i++) {
         int cur = numbers[depth];		// 함수의 깊이에 따라 숫자를 뽑는다.
         if (!isUsed[i]) {			// 연산자를 사용한 적이 있는지 확인
             isUsed[i] = true;			// 만약 없다면, 해당 연산자를 사용했다고 체크!
             int result = calc(sum, cur, operators[i]);	// 계산 식으로 이동.
             dfs(depth + 1, result);		// 재귀 호출 부분(깊이+1, 계산한 결과 값(result)를 전달)
             isUsed[i] = false;			// 재귀 호출이 모두 끝났다고 생각하고, 다시 비 방문 처리.
         }
     }
 }

재귀의 깊이(depth)로 연산할 숫자의 배열 인덱스로 사용하고, 재귀 함수 안에 for문으로 연산자 배열을 체크하면서, 계산을 해서 다시 재귀 호출을 하면서 파라미터로 (깊이, 연산한 결과 값) 를 넘겨준다.

 

연산하는 calc 함수 구현

static int calc(int sum, int num, String oper) {

	switch (oper) {
		case "+":   sum += num;   break;
		case "-":   sum -= num;   break;
		case "*":   sum *= num;   break;
		case "/":   sum /= num;   break;
	}
	return sum;
}

 

switch 문으로 파라미터로 넘어온 연산자(oper) 문자열에 따라 연산 결과를 리턴 한다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int MAX = Integer.MIN_VALUE; // 최대값
    static int MIN = Integer.MAX_VALUE; // 최소값
    static String[] operators;          // 연산자 배열
    static boolean[] isUsed;            // 연산자 사용 여부 체크
    static int[] numbers;               // 계산할 숫자 배열
    static int N;                       // 숫자 개수

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(bf.readLine());
        numbers = new int[N];
        operators = new String[N-1];
        isUsed = new boolean[N];

        /* numbers 받기 */
        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        /* operators 받기 */
        int index = 0;
        String oper = "+-*/";
        st = new StringTokenizer(bf.readLine());

        for (int i = 0; i < 4; i++) {
            int n = Integer.parseInt(st.nextToken());
            if (n > 0) {
                String op = oper.substring(i, i + 1);
                while (n-- > 0) {
                    operators[index++] = op;
                }
            }
        }        

        dfs(1, numbers[0]);

        System.out.println(MAX);
        System.out.println(MIN);
    }

    static void dfs(int depth, int sum) {

        /* 종료 조건 */
        if (depth == N) {
            if (MAX < sum)  MAX = sum;
            if (MIN > sum)  MIN = sum;
            return;
        }

        for (int i = 0; i < N - 1; i++) {
            int cur = numbers[depth];
            if (!isUsed[i]) {
                isUsed[i] = true;
                int result = calc(sum, cur, operators[i]);
                dfs(depth + 1, result);
                isUsed[i] = false;
            }
        }
    }

    static int calc(int sum, int num, String oper) {
        switch (oper) {
            case "+":   sum += num;   break;
            case "-":   sum -= num;   break;
            case "*":   sum *= num;   break;
            case "/":   sum /= num;   break;
        }
        return sum;
    }
}

 

반응형
저작자표시 (새창열림)
  1. 문제 분석
  2. 전체 코드
'📜 코딩테스트/BAEKJOON\백트래킹' 카테고리의 다른 글
  • 백준 14889번 : 스타트와 링크 (JAVA) 문제 풀이
  • 백준 9663번 : N-Queen (JAVA) 문제 풀이
  • 백준 15650번 : N과 M(2) (JAVA) 문제 풀이
  • 백준 15649번 : N과 M(1) (JAVA) 문제 풀이
iseunghan
iseunghan
꾸준하게 열심히..
iseunghan
iseunghan

공지사항

  • 어제보다 나은 오늘이 되기 위해 🔥
  • 분류 전체보기 (262)
    • 💐 Spring (14)
      • 개념 및 이해 (2)
      • Spring 핵심 기술 (24)
      • Spring REST API (8)
      • Spring MVC, DB 접근 기술 (7)
      • Spring Security (23)
      • Spring in Action (1)
    • 🌻 JAVA (84)
      • 자바 ORM 표준 JPA 프로그래밍 (20)
      • 알고리즘, 자료구조 (13)
      • 디자인 패턴 (7)
      • 정리정리정리 (43)
      • JUnit (1)
    • 🔖 Snippets (3)
      • Javascript (3)
    • ⚙️ Devops (22)
      • ⛏ Git (11)
      • 🐳 Docker (6)
      • 🐧 Linux (3)
      • 🌈 Jenkins (1)
      • 📬 Kafka (1)
    • 💬 ETC.. (4)
      • 💻 macOS (2)
    • 🌧️ ORM (2)
      • JPA (2)
    • 🐍 Python (3)
    • 📚 Databases (15)
      • 오라클로 배우는 데이터베이스 개론과 실습(2판) (3)
      • RealMySQL 8.0 (8)
    • 🔥 Computer Science (5)
      • 📡 네트워크 (5)
    • 🏷️ 협업 (1)
    • 📜 코딩테스트 (38)
      • BAEKJOON\수학 1, 수학 2 (8)
      • BAEKJOON\재귀 (5)
      • BAEKJOON\브루트 포스 (3)
      • BAEKJOON\정렬 (1)
      • BAEKJOON\백트래킹 (5)
      • BAEKJOON\BFS, DFS (6)
      • BAEKJOON\이분탐색 (1)
      • BAEKJOON\다이나믹 프로그래밍 (9)
      • BAEKJOON\그리디 알고리즘 (0)
    • ✨ ISEUNGHAN (1)

인기 글

전체
오늘
어제
반응형
hELLO · Designed By 정상우.
iseunghan
백준 14888번 : 연산자 끼워넣기 (JAVA) 문제 풀이
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.