2026.04.13 월

오늘의 문제!

2-SAT - 1_11277

import java.io.*;
import java.util.StringTokenizer;

public class SAT1_11277 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] clauses = new int[m][2];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            clauses[i][0] = Integer.parseInt(st.nextToken());
            clauses[i][1] = Integer.parseInt(st.nextToken());
        }

        boolean check = false;

        for (int i = 0; i < (1 << n); i++) {
            boolean flag = true;

            for (int j = 0; j < m; j++) {
                int a = clauses[j][0];
                int b = clauses[j][1];

                boolean valA = checkTrue(i, a);
                boolean valB = checkTrue(i, b);

                if (!valA && !valB) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                check = true;
                break;
            }
        }

        bw.write(check ? "1\n" : "0\n");
        bw.flush();
        bw.close();
    }

    static boolean checkTrue(int state, int x) {
        if (x < 0) {
            int target = -x - 1;
            return (state & (1 << target)) == 0;
        } else {
            int target = x - 1;
            return (state & (1 << target)) != 0;
        }
    }
}

어렵다... 각각 들어온 x1,x2,x3 ... 가 true일지 false일지 모든 경우의 수를 브루트포스로 확인하고 식이 하나라도 맞지 않으면 그냥 나가서 0 출력, 전부 통과하면 1 출력!

비트마스킹 심화기술.. 어렵다 어려워!