학습용 공간

골드바흐의 추측과

에라토스테네스의 체를 활용 

위 두 개념은 starmk95.tistory.com/45 링크에서 설명

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer> prime;
    static boolean[] check;
    public static void main(String[] args) {
        prime = new ArrayList<>();
        findPrime();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 테스트 케이스의 개수
        for (int i=0;i<n;i++) {
            int even = sc.nextInt(); // 짝수 입력 받기
            findPartitionNum(even);
        }
    }

    // 먼저 2 이상 1000000 이하의 소수들을 구한다. (입력 범위 내의 소수)
    // 소수들을 구하기 위해서는 에라토스테네스의 체를 사용한다.
    // 약 0.01초보다 덜 걸림
    public static void findPrime() {
        check = new boolean[1000001]; // 에라토스테네스의 체 구현 (true면 지워진 것, false면 지워지지 않은 것)
        for (int i=2;i<=1000000;i++) {
            if (!check[i]) { // 지워지지 않은 가장 작은 값을 구하기
                prime.add(i); // 해당 수는 소수이다. (소수 리스트에 추가)
            }
            for (int j=i*2;j<=1000000;j+=i) {
                // i의 최대값이 1000000이므로 i*i가 int 범위를 넘어가기 때문에 i*2부터 시작
                // i가 백만 이하의 수라면 i*i가 int의 범위 이내이므로 i*i부터 시작
                // i*i부터 시작하는 이유는 i*i보다 작은 i의 배수들은 이미 i보다 작은 소수들의 배수에 의해 처리되었기 때문에
                // 따로 처리할 필요가 없기 때문이다.
                check[j] = true; // 소수의 배수들 지워주기
            }
        }
    }

    public static void findPartitionNum(int even) {
        int cnt = 0; // 골드바흐 파티션의 개수
        for (int x : prime) { // 범위 내 모든 소수들에 대해 확인
            if (x <= even/2) { // 두 소수의 합의 순서만 다른 것은 같은 파티션 취급하므로 짝수의 반보다 같거나 작은 소수들에 대해 판별
                if (!check[even-x]) cnt+=1; // 짝수에서 해당 소수를 뺀 값이 소수라면 파티션 개수 하나 증가
            } else break; // 짝수의 반보다 큰 값에 대해서는 처리할 필요 없음 (중복이거나 소수다 짝수보다 큰 경우임)
        }
        System.out.println(cnt); // 해당 짝수의 골드바흐 파티션의 개수 출력
    }
}

문제 출처 : www.acmicpc.net/problem/17103

먼저 A진법 수를 10진법으로 변환하고,

변환된 10진법 수를 B진법으로 변환한다.

import java.util.Scanner;

public class Main {
    static int[] num;
    static int A;
    static int B;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        A = sc.nextInt();
        B = sc.nextInt();
        int m = sc.nextInt();
        num = new int[m];
        for (int i=m-1;i>=0;i--) { // 낮은 자리 수일수록 낮은 인덱스에 저장
            num[i] = sc.nextInt();
        }
        toB(to10());
        System.out.println();
    }
    /*
    1. 먼저 A진법 수를 10진법으로 바꾼다.
    2. 10진법으로 바뀐 수를 B진법으로 바꾼다.
     */

    // A진법 10진법으로 바꾸는 메소드
    public static int to10() {
        int num10 = 0;
        for (int i=0;i<num.length;i++) {
            num10 += num[i]*(int)Math.pow(A, i); // 각 자리에 맞게 A^n값 곱해서 10진수로 바꿔줌
        }
        return num10; // 10진수로 바꾼 값 저장
    }

    // 10진법 B진법으로 바꾸는 메소드
    public static void toB(int n) {
        if (n == 0) return;
        toB(n/B);
        System.out.print(n%B + " ");
    }
}

문제 출처 : www.acmicpc.net/problem/11576

일반적인 진수 변환법을 적용해서 푸는데

음수/음수의 경우 발생하는 예외를 처리해주어야한다.

주석 참고

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        if (num == 0) {
            System.out.println(0);
        } else {
            convert(num);
            System.out.println();
        }
    }

    /*
    진수 변환법
    2진수일 때,
    10 = 2*5 + 0
    5 = 2*2 + 1
    2 = 2*1 + 0
    1 = 2*0 + 1
    이에 따라, 10을 2진수로 표현하면 1010이된다.

    -2진수도 위와 같은 진수 변환법을 사용하면 된다.
    다만 주의할 점은 음수/음수인 경우의 처리이다.
    이 경우에만 나머지가 -1이 나오기 때문에 다르게 처리해주어야 한다.
    (나머지를 1로 만들기 위해서는 몫이 1만큼 커져야함)
    -13 = (-2)*7 + 1 이다.
    그러나 -13/-2의 결과는 6이 나온다.
    그러므로 -13-1/-2 처리를 해주어야 정상적인 7 값이 나온다.
    -13 = -2*(7) + 1
    7 = -2*(-3) + 1
    -3 = -2*(2) + 1
    2 = -2*(-1) + 0
    -1 = -2*(1) + 1
    1 = -2*(0) + 1
     */

    public static void convert(int n) {
        if (n == 0) return; // n이 0이면 변환 끝난 것임
        if (n%2 == 0) { // n이 짝수이면
            convert(n/-2);
            System.out.print(0); // 2로 나누어 떨어지므로 0
        } else { // n이 홀수이면
            if (n>0) convert(n/-2);
            else convert((n-1)/-2); // 음수/음수인 경우 -> 처리 필요
            System.out.print(1); // 2로 나누어 떨어지지 않으므로 1
        }
    }

}

문제 출처 : www.acmicpc.net/problem/2089

그래프의 정점의 집합을 둘로 분할하여,

각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때,

그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

dfs로 정점들을 탐색하며 간선으로 연결된 정점들은 다른 집합에 속하도록 한다.

check[x] == 1 또는 2 // 집합 1 또는 2에 넣기 (0이면 방문 안한 정점)

입력 예제는 성공했지만 계속 4초에서 3초로 넘어가는 중에 실패처리가 나와서 의문이였는데

그래프가 2개 이상의 연결요소로 구성된 경우를 처리하지 않았기 때문이라는 것을 깨달았다.

(그래프의 모든 정점들이 연결되어 있지 않고 섬처럼 떨어져 있을 수도 있다는 것)

import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph; // 인접리스트로 그래프 구현
    static int[] check; // 각 정점의 방문여부와 소속 집합을 기록 (0:방문안함, 1:집합1, 2:집합2)

    static void dfs(int x, int prevGroup) {
        if (prevGroup == 1) check[x] = 2;
        else if (prevGroup == 2) check[x] = 1;
        for (int y : graph[x]) {
            if (check[y] == 0) { // 방문 안한 정점이면
                dfs(y, check[x]);
            }
        }
    }

    static String checkBipartite(int vertex) {
        for (int i=1;i<=vertex;i++) { // 모든 정점과 연결된 정점들에 대해 확인
            for (int x : graph[i]) { // (모든 간선을 확인)
                if (check[i] == check[x]) { // 간선으로 연결된 간선이 같은 집합에 속하면
                    return "NO"; // 이분 그래프가 아님
                }
            }
        }
        return "YES"; // 위 루프를 모두 통과하면 이분 그래프가 맞음
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cases = sc.nextInt(); // 테스트 케이스 개수
        for (int i=0;i<cases;i++) {
            int n = sc.nextInt(); // 정점의 개수
            int m = sc.nextInt(); // 간선의 개수
            graph = (ArrayList<Integer>[]) new ArrayList[n+1]; // 정점의 개수만큼 리스트를 원소로 갖는 배열 생성
            for (int j=1;j<=n;j++){
                graph[j] = new ArrayList<Integer>(); // 각 정점마다 리스트 생성
            }
            for (int j=0;j<m;j++) { // 간선 저장
                int u = sc.nextInt();
                int v = sc.nextInt();
                graph[u].add(v);
                graph[v].add(u);
            }
            check = new int[n+1]; // 각 정점에 대한 방문 여부와 집합 기록 배열 생성
            // 그래프를 구성하는 연결요소가 2개 이상일 수도 있기 때문에
            // dfs 수행하고도 방문하지 않은 정점이 있는지 확인해야 함
            for (int j=1; j<=n; j++) {
                if (check[j] == 0) {
                    dfs(j, 1);
                }
            }
            System.out.println(checkBipartite(n));
        }
    }
}

문제 출처 : https://www.acmicpc.net/problem/1707

그래프의 연결 요소를 확인하는 방법은

임의의 정점에서 DFS 또는 BFS 탐색을 수행한 후에도 

방문하지 않은 정점이 남아있다면, 

다른 연결요소가 있다는 특성을 이용한 것이다.

모든 정점들에 대하여 각 정점을 방문했는지 확인하고, 

방문하지 않은 정점이 있다면 연결요소의 개수를 1개 추가하고

해당 정점에서 다시 탐색을 수행한다.

import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph; // 인접 리스트로 그래프 구현
    static boolean[] check; // 정점 방문 여부 확인하는 배열

    static void dfs(int x) {
        if (check[x]) return; // 이미 방문한 정점이면 해당 정점에서는 탐색 안함
        check[x] = true; // 정점 방문 체크
        for (int y : graph[x]) {
            if (!check[y]) { // x와 연결된 정점 y를 방문하지 않았으면
                dfs(y); // 정점 y 방문해서 탐색 수행
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // n = 정점의 개수
        int m = sc.nextInt(); // m = 간선의 개수
        // 그래프 구현
        graph = (ArrayList<Integer>[]) new ArrayList[n+1];
        for (int i=1;i<=n;i++) graph[i] = new ArrayList<Integer>();
        for (int i=0;i<m;i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }
        boolean flag = true; // 모든 연결요소 확인했으면 true, 아니면 false
        int compNum = 0; // 연결 요소의 개수
        // 정점 방문 여부 초기화
        check = new boolean[n+1];
        for (int i=1;i<=n;i++) { // 모든 정점에 대해 반복문 돌림
            if (!check[i]) { // 방문 안한 정점이 있다는 것은 확인 안한 연결요소가 있다는 것
                compNum+=1; // 연결요소 수 추가
                dfs(i); // 해당 연결요소 탐색 수행
            }
        } // 모든 정점이 방문 처리되었으면 모든 연결요소를 확인한 것임
        // 확인된 연결요소의 개수 출력
        System.out.println(compNum);
    }
}

문제 출처 : https://www.acmicpc.net/problem/11724

리스트(그래프)의 원소(정점) 접근은 for each문을 사용하여 처리한다.

(for문과 get()메소드로 인덱스를 사용해 접근하는 것보다 빠르기 때문)

위의 이유에 대해서는 하단 링크 참고

https://starmk95.tistory.com/110 

인접 리스트를 사용해 그래프를 구현했고

DFS는 재귀, BFS는 Queue를 통해 구현했다.

import java.util.*;

public class Main {

    static ArrayList<Integer>[] graph; // 인접리스트 방식으로 그래프 저장
    static boolean[] check; // 정점 방문 여부를 확인하는 배열
    // 리스트(그래프)의 원소(정점) 접근은 for each문을 사용하여 처리
    // (for문과 get()메소드로 인덱스를 사용해 접근하는 것보다 빠르기 때문)

    static void dfs(int x) {
        if (check[x]) return; // 이미 방문한 적이 있는 정점이라면 해당 정점 탐색하지 않음
        check[x]= true; // 방문한 정점 체크
        System.out.print(x + " "); // 정점 방문하면 출력
        for (int y : graph[x]) { // 각 정점에 연결되어 있는 정점들 모두에 대해 확인 (리스트에도 for each문 적용 가능)
            if (!check[y]) { // 방문한 적이 없는 정점이라면
                dfs(y); // 해당 정점을 방문하고 그 정점에서 dfs 수행
            }
        }
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(start); // 처음으로 bfs 탐색을 시작할 정점을 큐에 추가
        check[start] = true; // 정점 방문 체크
        while (!queue.isEmpty()) { // 큐가 비면 모든 탐색을 완료한 것임
            int x = queue.remove(); // bfs 탐색을 수행할 현재 정점
            System.out.print(x + " "); // 정점 방문하면 출력
            for (int y : graph[x]) { // bfs를 수행하는 정점에 연결된 모든 정점들 확인
                if (!check[y]) { // 정점을 방문하지 않았다면
                    queue.add(y); // 정점 방문
                    check[y] = true; // 정점 방문 체크
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
        int e = sc.nextInt();
        int start = sc.nextInt();
        graph = (ArrayList<Integer>[]) new ArrayList[v+1];
        for (int i=1;i<=v;i++) { // 각 배열의 원소(정점)에 대해 리스트 생성
            graph[i] = new ArrayList<Integer>();
        }
        // 각 배열의 원소는 각 정점에 해당한 정점들을 저장하는 리스트로 구성된다.
        for (int i=0;i<e;i++) {
            int temp1 = sc.nextInt();
            int temp2 = sc.nextInt();
            // 양 정점 모두에 add 해주어야 함 (undirected edge이기 때문)
            graph[temp1].add(temp2);
            graph[temp2].add(temp1);
        }
        // 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하는 조건을 충족하기 위한 정렬
        for (int i=1;i<=v;i++) Collections.sort(graph[i]);

        check = new boolean[v+1]; // dfs 수행 전에 정점 방문 여부 배열 초기화
        dfs(start);
        System.out.println();
        check = new boolean[v+1]; // bfs 수행 전에 정점 방문 여부 배열 초기화
        bfs(start);
        
    }
}

문제 출처 : https://www.acmicpc.net/problem/1260

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String temp;
        while ((temp = br.readLine()) != null) { // eof 처리
            int upper = 0;
            int lower = 0;
            int num = 0;
            int space = 0;
            for (int i=0;i<temp.length();i++){
                char c = temp.charAt(i);
                if (Character.isUpperCase(c)) upper+=1;
                else if (Character.isLowerCase(c)) lower+=1;
                else if (Character.isDigit(c)) num+=1;
                else if (Character.isSpaceChar(c)) space+=1;
            }
            System.out.printf("%d %d %d %d\n", lower, upper, num, space);
        }
    }
}

문제 출처 : https://www.acmicpc.net/problem/10820

문제가 쉬워보이는데 오답률이 높길래 의아해서 풀었다가 나도 틀려서 당황한 문제

문제의 요구사항(조건)을 잘 확인해야 한다는 것을 느낄 수 있는 문제였다.

문제의 포인트는 알맞는 자료형을 사용하는 것

문제에서 주어지는 4개의 자연수의 각 최대 값은 1,000,000

A와 B를 이어붙인 수는 10,000,001,000,000이 되는데, 이는 int 자료형의 범위를 넘어간다.

그러므로 long 자료형을 사용해서 A, B와 C, D가 이어진 수와 그 합을 처리해줘야한다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        String B = sc.next();
        String C = sc.next();
        String D = sc.next();

        String AB = A + B;
        String CD = C + D;

        long sum = Long.parseLong(AB) + Long.parseLong(CD);
        System.out.println(sum);
    }
}

문제 출처 : https://www.acmicpc.net/problem/10824

해당 문제를 해결하기 위해

괄호에 의한 우선 순위 뿐만 아니라

사칙연산의 연산자들 간의 우선 순위도 고려해야 한다.

(괄호) > *, / (곱셈, 나눗셈)  > +, - (덧셈, 뺄셈)

# 알고리즘

모든 수식의 입력들 처리할 때까지 반복

1. 입력이 피연산자(알파벳)이면

바로 출력문에 append()

2. 입력이 열린 괄호 "("이면

바로 출력문에 append()

3. 입력이 + 또는 - 이면 

   1) 스택이 비어있다면 바로 push()

   2) 스택이 비어있지 않다면 계속 pop()하고 append()

      a) 스택이 비면 중지

      b) 열린 괄호 "("를 만나면 중지

      a 또는 b 과정 끝나면 입력된 연산자 push

4. 입력이 * 또는 / 이면

   1) 스택이 비어있다면 바로 push()

   2) 스택이 비어있지 않다면 계속 pop()하고 append()

      a) 스택이 비면 중지

      b) 열린 괄호 "("를 만나면 중지

      c) 우선순위 낮은 연산자 + 또는 - 를 만나면 중지

      a 또는 b 또는 c 과정 끝나면 입력된 연산자 push

5. 입력이 닫힌 괄호 ")"이면

스택에서 열린 괄호 "("가 나올 때까지 pop()하고 append()

모든 수식의 입력들을 처리한 후에

스택에 남아있는 연산자가 있다면 모두 pop()하고 append()

완성된 출력문 출력

아래는 문제를 해결하는 코드이다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        Scanner sc = new Scanner(System.in);
        String inorder = sc.next();
        String[] each = inorder.split("");
        StringBuilder sb = new StringBuilder();
        for (String x : each) {
            if (x.equals(")")) { // 닫힌 괄호가 들어오면 stack에 열린 괄호가 나올 때까지 pop하고 식에 append 해줌
                while (!stack.peek().equals("(")) {
                    sb.append(stack.pop());
                }
                stack.pop(); // "(" stack에서 제거
            } else if (x.equals("+") || x.equals("-")) {
                // +,-연산자가 들어올 때
                // stack이 비거나 열린 괄호가 나오거나
                // stack에 있는 우선 순위가 같은 +, - 연산자들은 append 해준다. (stack에는 열린 괄호와 연산자만 들어감)
                if (stack.empty()) {
                    // stack이 비어있으면
                    stack.push(x);
                } else {
                    // stack이 비어있지 않으면
                    while (!stack.empty()) {
                        // 열린 괄호를 만나면 pop과 append 중지
                        if (stack.peek().equals("(")) break;
                        // 아니라면 stack이 빌때까지 pop하고 append
                        sb.append(stack.pop());
                    }
                    stack.push(x);
                }
            } else if (x.equals("*") || x.equals("/")) {
                if (stack.empty()) {
                    // stack이 비어있으면
                    stack.push(x);
                } else {
                    // stack이 비어있지 않으면
                    while (!stack.empty()) {
                        // 열린 괄호를 만나면 pop과 append 중지
                        if (stack.peek().equals("(")) break;
                        // *, /보다 우선 순위가 낮은 +, - 연산자를 만나면 pop과 append 중지
                        else if (stack.peek().equals("+") || stack.peek().equals("-")) break;
                        // 아니라면 pop하고 append
                        sb.append(stack.pop());
                    }
                    stack.push(x);
                }
            } else if (x.equals("(")) {
                // 열린 괄호가 들어와도 stack에 넣어준다.
                stack.push(x);
            } else {
                // 피연산자가 들어오면 바로 append
                sb.append(x);
            }
        }
        // 반복문을 다 돌고도 stack에 남아있는 연산자가 있다면
        // -> 열림 괄호 없이 들어온 연산자가 있었을 경우 처리
        while (!stack.empty()) sb.append(stack.pop());

        System.out.print(sb);
    }
}

문제 출처 : https://www.acmicpc.net/problem/1918

import java.util.*;
class Edge { // 간접 리스트를 위한 클래스
    int from, to;
    Edge(int from, int to) {
        this.from = from;
        this.to = to;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 사람 수
        int m = sc.nextInt(); // 관계 수

        boolean[][] a = new boolean[n][n]; // 인접 행렬 구현
        ArrayList<Integer>[] g = (ArrayList<Integer>[]) new ArrayList[n]; // 인접 리스트 구현
        ArrayList<Edge> edges = new ArrayList<Edge>(); // 간접 리스트 구현
        for (int i=0;i<n;i++) { // 인접 리스트는 각 정점마다 연결된 간선을 저장하므로
            g[i] = new ArrayList<>(); // 각 정점에 대해 리스트를 할당
        }
        for (int i=0; i<m; i++) {
            // 친구 관계는 양방향 관계이므로 양 방향으로 간선을 배정해야 한다.
            // 간선 리스트에 관계 저장
            int from = sc.nextInt();
            int to = sc.nextInt();
            edges.add(new Edge(from, to));
            edges.add(new Edge(to, from));
            // 인접 행렬에 관계 저장
            a[from][to] = a[to][from] = true;
            // 인접 리스트에 관계 저장
            g[from].add(to);
            g[to].add(from);
        }
        // 관계는 양방향이므로 입력된 관계*2를 해주어야 간선들의 총 개수가 된다.
        m *= 2;
        // 아래는 2개의 간선들에 대한 관계 파악해줌
        for (int i=0;i<m;i++) {
            for (int j=0;j<m;j++) {
                // 간선리스트 사용
                int A = edges.get(i).from;
                int B = edges.get(i).to;
                int C = edges.get(j).from;
                int D = edges.get(j).to;
                // B-C 친구 관계 여부를 간선 리스트로 확인
                // 서로 다른 두 간선이 연결되어 있는지 확인
                // A-B, C-D가 친구일 때 B-C가 친구인지 확인하는 것
                if (A == B || A == C || A == D || B == C || B == D || C == D) {
                    // A==B이면 edges i는 간선이 아님
                    // A==C 또는 A==D는 간선 i와 j가 정점 1개를 공유하는 간선이라는 것이다.
                    // (서로 다른 정점 4개를 연결하는 간선이 아닌 것임)
                    continue; // 위 조건에 해당하면 A-B, C-D가 친구일 때 B-C가 친구인지 확인할 수 없으므로 continue (정점 4개에 대한 관계가 아니게 되기 때문)
                }
                // 인접 행렬 사용
                if (!a[B][C]) continue; // A-B, C-D 에서 B-C 관계도 성립하지 않는다면 continue
                // 인접 리스트 사용
                for (int E : g[D]) { // D 정점과 연결된 정점들이 E로 들어온다.
                    if (A == E || B == E || C == E || D == E) continue;
                    // 연결된 정점이 A, B, C, D와 같다면 이는 중복되는 간선이 들어온 것이므로 continue
                    // (D-E 관계에 해당하지 않는다는 것)
                    // 위 조건들을 모두 통과하면 A-B-C-D-E 관계가 존재한다는 것이다.
                    System.out.println(1);
                    System.exit(0);
                }
            }
        }
        // 위 모든 쌍의 간선들을 확인했음에도 불구하고 모두 조건문에 걸려 continue 처리되어
        // 해당 코드에 다다르면 A-B-C-D-E 관계가 성립하지 않는다는 것이다.
        System.out.println(0);
    }
}

문제 출처 : https://www.acmicpc.net/problem/13023

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] num = new int[n][m];
        for (int i=0; i<n; i++) {
            String s = sc.next();
            for (int j=0; j<m; j++) {
                num[i][j] = s.charAt(j) - '0'; // char형을 int 형으로 바꾸는 방법
            }
        }
        // 비트마스크 - 브루트포스
        // 각 칸을 가로로 놓을지 세로로 놓을지 모든 경우의 수를 확인
        int ans = 0;
        for (int i=0;i<(1<<(n*m));i++) {
            int sum = 0;
            // 가로로 놓는 경우
            for (int j=0;j<n;j++) {
                int cur = 0; // 현재 이어진 가로칸들로 구성된 수
                for (int k=0;k<m;k++) {
                    int index = j*m+k; // 2차원 배열을 1차원 배열로 보았을 때, i행 j열은 앞에 i*m+(j-1)개의 원소들이 있기 때문
                    if ((i&(1<<index)) == 0) { // 가로이면
                        cur = cur*10 + num[j][k];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }
                sum+=cur;
            }
            // 세로로 놓는 경우
            for (int j=0;j<m;j++) {
                int cur = 0;
                for (int k=0;k<n;k++) {
                    int index = k*m+j;
                    if ((i&(1<<index)) != 0) { // 세로이면
                        cur = cur*10 + num[k][j];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }
            ans = Math.max(ans, sum);
        }
        System.out.println(ans);
    }
}

문제 출처 : https://www.acmicpc.net/problem/14391

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        int[] num = new int[n];
        for (int i=0;i<n;i++) {
            num[i] = sc.nextInt();
        }
        // 비트마스크 - 브루트포스
        // 만들 수 있는 부분 집합들의 경우의 수들을 정수로 표현했음 (공집합 제외)
        // 1부터 2^n까지
        int cnt = 0; // 부분 수열의 합이 같은 경우의 수를 세기 위한 변수

        for (int i=1;i<(1<<n);i++) { // 만들 수 있는 모든 부분 집합들에 대해 반복
            int sum = 0;
            for (int j=0;j<n;j++) {
                if((i&(1<<j)) != 0) { // 정수로 표현한 부분 집합 i에 j가 들어있다면
                    sum += num[j];
                }
            }
            if (sum == s) { // 해당 부분집합 i에 들어있는 모든 정수들을 더한 값이 s와 같으면
                cnt+=1;
            }
        }

        System.out.println(cnt);
    }
}

문제 출처 : https://www.acmicpc.net/problem/1182