www.acmicpc.net/problem/2422

 

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번

www.acmicpc.net

섞으면 안되는 조합이 입력으로 주어지고 3개 조합이 가능한 방법이 몇 개 있는지 출력하는 문제입니다.

 

저는 섞으면 안되는 조합을 2차원배열로 표시하였습니다.

조합이 x, y로 주어지면

visit[x][y] = true;

visit[y][x] = true;

여기서 true로 표시하는 것은 x번과 y번은 섞으면 안되는 조합이라는 것입니다.

 

그 다음 재귀를 돌리는데 매개변수를 pre(이전에 골랐던 번호), now(방금 고른 번호), cnt(고른 갯수)로 하였고

반복문으로 마지막 고를 번호 i를 고릅니다.

 

i를 고를 때 첫번째로 고른 pre와 두번째로 고른 now와 섞으면 안되는 조합인지 확인한 후에 다음으로 넘겨줍니다.

 

마지막으로 3개를 모두 골랐으면 ans를 1 증가시킵니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static boolean noMix[][];
    static int N, M, ans;
 
    static void func(int pre, int now, int cnt) {
        if (cnt == 3) {
            ans++;
            return;
        }
 
        for (int i = now + 1; i <= N; i++) {
            if (noMix[now][i])
                continue;
            if (pre != -1 && noMix[pre][i])
                continue;
 
            func(now, i, cnt + 1);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        noMix = new boolean[N + 1][N + 1];
        int x, y;
 
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            noMix[x][y] = true;
            noMix[y][x] = true;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(-1, 0, 0);
        System.out.println(ans);
    }
}
cs

'algorithm > Bruteforce' 카테고리의 다른 글

boj 17281 ⚾  (0) 2021.02.16
boj 3040 백설 공주와 일곱 난쟁이  (0) 2021.02.15
boj 2961 도영이가 만든 맛있는 음식  (0) 2021.02.15
boj 1018 체스판 다시 칠하기  (0) 2021.01.29
boj 15686 치킨 배달  (0) 2021.01.22

www.acmicpc.net/problem/1018

 

1018번: 체스판 다시 칠하기

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

www.acmicpc.net

브루트포스 문제로 8*8 크기씩 계속 비교해가며 다시 칠해야할 갯수의 최솟값을 구해야합니다.

 

cnt1 => 맨 왼쪽 위 칸이 B로 칠해질 경우

cnt2 => 맨 왼쪽 위 칸이 W로 칠해질 경우

 

cnt1의 경우에는 i가 짝수일 때 BWBWBWBW, 홀수일 때 WBWBWBWB를 만들어야 합니다.

cnt2의 경우에는 i가 짝수일 때 WBWBWBWB, 홀수일 때 BWBWBWBW를 만들어야 합니다.

 

각 인덱스에서 다른색이 칠해져있으면 해당cnt를 증가시켜줍니다.

이 과정을 8*8 크기만큼 반복하여 최솟값을 출력합니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char ch[][];
    static int N, M, ans = 2500;
 
    static void func(int x, int y) {
        int cnt1 = 0;
        int cnt2 = 0;
        for (int i = x; i < x + 8; i++) {
            for (int j = y; j < y + 8; j++) {
                if (i % 2 == 0) {
                    if (j % 2 == 0) {
                        if (ch[i][j] == 'B')
                            cnt2++;
                        else
                            cnt1++;
                    } else {
                        if (ch[i][j] == 'B')
                            cnt1++;
                        else
                            cnt2++;
                    }
                } else {
                    if (j % 2 == 0) {
                        if (ch[i][j] == 'B')
                            cnt1++;
                        else
                            cnt2++;
                    } else {
                        if (ch[i][j] == 'B')
                            cnt2++;
                        else
                            cnt1++;
                    }
                }
            }
        }
 
        ans = Math.min(ans, Math.min(cnt1, cnt2));
    }
 
    static void solve() {
        for (int i = 0; i <= N - 8; i++) {
            for (int j = 0; j <= M - 8; j++) {
                func(i, j);
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        ch = new char[N][M];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            ch[i] = st.nextToken().toCharArray();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        solve();
    }
}
 cs

'algorithm > Bruteforce' 카테고리의 다른 글

boj 17281 ⚾  (0) 2021.02.16
boj 3040 백설 공주와 일곱 난쟁이  (0) 2021.02.15
boj 2961 도영이가 만든 맛있는 음식  (0) 2021.02.15
boj 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데  (0) 2021.01.29
boj 15686 치킨 배달  (0) 2021.01.22

www.acmicpc.net/problem/10096

 

10096번: 세 친구

준규, 해빈, 진욱이는 다음과 같은 게임을 한다. 먼저, 준규가 문자열 S를 고른다. 그 다음, 해빈이는 S의 뒤에 S를 붙인 새로운 문자열 T를 만든다. 마지막으로 진욱이는 문자열 T의 어딘가(시작이

www.acmicpc.net

문자열 S가 2번 반복되어있는 문자열에 문자 하나를 무작위로 넣었습니다.

 

이렇게 완성된 문자열에서 문자열 S를 찾는 문제입니다.

 

일단 같은 문자열이 2번 반복되어있기때문에 주어지는 입력은 홀수개의 문자로 이루어져 있습니다. (2n+1개)

저는 이 문자열은 앞에서부터

n, n+1개로 끊은 문자열 2개

n+1, n개로 끊은 문자열 2개

이렇게 그룹을 나누었습니다.

 

나눈 문자열을 순차적으로 비교를 하였고,

다른부분이 1개면 S는 n개로 끊었던 문자열이 되고, 2개 이상이면 S를 구할 수 없는 것입니다.

 

두 개의 그룹이

모두 true면 답이 2개이므로 2개가 같으면 문자열 출력, 다르면 NOT UNIQUE

모두 false면 답이 없으므로 NOT POSSIBLE

아니면 true인 경우의 문자열을 출력해주시면 됩니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char ch[];
    static int N;
 
    static boolean solve(char s1[], char s2[]) {
        int cnt = 0;
        for (int i = 0, j = 0; i < s1.length; i++, j++) {
            if (s1[i] != s2[j]) {
                if (cnt > 0)
                    return false;
                cnt++;
                i--;
            }
        }
 
        return true;
    }
 
    static void func() {
        if (N % 2 == 0) {
            System.out.println("NOT POSSIBLE");
            return;
        }
        char s1[] = new char[N / 2];
        char s2[] = new char[N / 2 + 1];
        char s3[] = new char[N / 2];
        char s4[] = new char[N / 2 + 1];
 
        System.arraycopy(ch, 0, s1, 0, N / 2);
        System.arraycopy(ch, N / 2, s2, 0, N / 2 + 1);
 
        System.arraycopy(ch, 0, s4, 0, N / 2 + 1);
        System.arraycopy(ch, N / 2 + 1, s3, 0, N / 2);
 
        boolean result2 = solve(s3, s4);
        boolean result1 = solve(s1, s2);
 
        if (result1 && result2) {
            String str1 = String.valueOf(s1);
            String str2 = String.valueOf(s3);
            if (str1.contains(str2))
                System.out.println(String.valueOf(s1));
            else
                System.out.println("NOT UNIQUE");
        } else if (!result1 && !result2)
            System.out.println("NOT POSSIBLE");
        else if (result1)
            System.out.println(String.valueOf(s1));
        else
            System.out.println(String.valueOf(s3));
 
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        ch = st.nextToken().toCharArray();
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

'algorithm > String' 카테고리의 다른 글

boj 10453 문자열 변환  (0) 2024.07.24
boj 9081 단어 맞추기  (0) 2021.12.15

www.acmicpc.net/problem/17528

 

17528번: Two Machines

스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 ti를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나

www.acmicpc.net

2019 icpc 지역예선 L번이고, 2020 icpc 예비소집 문제였습니다.

 

icpc 예선 때 그리디로 접근을 해봤을때 WA를 받아서 결국 못풀었는데 이게 dp라고해서 당황했던 기억이 있습니다.....

 

newdeal123.tistory.com/5

 

[BOJ][백준]DP-17528번 Two Machines

https://www.acmicpc.net/problem/17528 17528번: Two Machines 문제 스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각..

newdeal123.tistory.com

 

이후에 위의 블로그에서 얻은 정보를 바탕으로 2020년 icpc 예비소집때는 AC를 받을 수 있었습니다!

하지만 냅색방법으로 푸는 것이 효율이 더 좋다고 합니다.

저는 냅색을 잘 이해하지 못해서 이해하는데 성공했던 이 방법으로 하였습니다.

 

우선 dp의 구성은

dp[index][해당 기계의 현재 남은 작업량][A기계 or B기계] => 최소시간

이렇게 하였습니다.

 

만약 A 기계가 now만큼의 작업을 수행중일 때 3가지를 고려하여야 합니다.

1. 다음 작업을 A기계가 수행하는 경우

    => 그냥 A의 작업량을 추가하면 됩니다.

2. 다음 작업을 B기계가 수행하는 경우 & now보다 다음 작업량이 많을 경우

    => 작업이 B로 넘어가며, now만큼의 작업을 수행한 후에 next - now를 재귀로 넘겨줍니다.

3. 다음 작업을 B기계가 수행하는 경우 & now보다 다음 작업량일 적을 경우

    => 그대로 A가 작업하며, now-next를 재귀로 넘겨줍니다.

 

이 과정을 반복하시면 되겠습니다.

 

시간이 되면 냅색문제 개념부터 차근차근 봐야겠습니다..

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 1000000000
using namespace std;
 
int dp[251][62501][2];
int list1[251], list2[251], N;
 
int func(int idx, int now, int t) {
    if (idx == N + 1) return now;
 
    if (dp[idx][now][t] != -1) return dp[idx][now][t];
    dp[idx][now][t] = INF;
 
    if (t) {
        dp[idx][now][t] = min(dp[idx][now][t], func(idx + 1, now + list1[idx], t));
 
        if (now < list2[idx]) {
            dp[idx][now][t] = min(dp[idx][now][t], func(idx + 1, list2[idx] - now, 1 - t) + now);
        }
        else {
            dp[idx][now][t] = min(dp[idx][now][t], func(idx + 1, now - list2[idx], t) + list2[idx]);
        }
    }
    else {
        dp[idx][now][t] = min(dp[idx][now][t], func(idx + 1, now + list2[idx], t));
 
        if (now < list1[idx]) {
            dp[idx][now][t] = min(dp[idx][now][t], func(idx + 1, list1[idx] - now, 1 - t) + now);
        }
        else {
            dp[idx][now][t] = min(dp[idx][now][t], func(idx + 1, now - list1[idx], t) + list1[idx]);
        }
    }
 
    return dp[idx][now][t];
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list1[i] >> list2[i];
    }
    memset(dp, -1, sizeof(dp));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(1, 0, 0) << '\n';
 
    return 0;
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 5557 1학년  (0) 2021.02.05
boj 5573 산책  (0) 2021.02.04
boj 9657 돌 게임 3  (0) 2021.01.27
boj 2096 내려가기  (0) 2021.01.22
boj 1103 게임  (0) 2021.01.22

www.acmicpc.net/problem/15663

 

15663번: N과 M (9)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

N과M 9번째 문제입니다.

 

다른 문제들과 다른 점은 배열에 중복되는 숫자가 포함되어 주어진다는 것입니다.

 

결과를 출력하였을 때 중복 값을 제외하고 출력해야해서 Set에 ArrayList를 넣어 중복체크를 하였습니다.

 

수열은 오름차순으로 이루어져야한다는 말이 없으니 0번 인덱스부터 계속 돌려주시면 됩니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> list, ans;
    static int N, M;
    static boolean visit[];
    static Set<ArrayList<Integer>> s = new HashSet<>();
 
    static void dfs(int cnt) {
        if (cnt == M) {
            if (s.contains(ans))
                return;
 
            s.add(ans);
            for (int i = 0; i < ans.size(); i++) {
                sb.append(ans.get(i) + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = 0; i < N; i++) {
            if (visit[i])
                continue;
 
            int x = list.get(i);
 
            visit[i] = true;
            ans.add(x);
            dfs(cnt + 1);
            ans.remove(cnt);
            visit[i] = false;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();
        ans = new ArrayList<>();
        visit = new boolean[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(list);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0);
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 15665 N과 M (11)  (0) 2021.01.30
boj 15664 N과 M (10)  (0) 2021.01.30
boj 15657 N과 M (8)  (0) 2021.01.27
boj 15656 N과 M (7)  (0) 2021.01.27
boj 15655 N과 M (6)  (0) 2021.01.27

www.acmicpc.net/problem/15657

 

15657번: N과 M (8)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

N과M 8번째 문제입니다.

 

배열에서 M개를 고른 수열을 구하는데

같은 수를 여러번 사용해도되며 비내림차순으로 이루어진 수열이어야 합니다.

 

중복이 가능하기 때문에 방문체크는 하지않고,

비내림차순이므로 dfs를 돌리는 과정에서 ans에 추가했던 인덱스를 +1하지 않고 그대로 재귀로 보내버리는 식으로 하였습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> list, ans;
    static int N, M;
 
    static void dfs(int idx, int cnt) {
        if (cnt == M) {
            for (int i = 0; i < ans.size(); i++) {
                sb.append(ans.get(i) + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = idx; i < N; i++) {
            int x = list.get(i);
 
            ans.add(x);
            dfs(i, cnt + 1);
            ans.remove(cnt);
        }
    }
 
    static void input() throws Exception {
        list = new ArrayList<>();
        ans = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(list);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0, 0);
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 15664 N과 M (10)  (0) 2021.01.30
boj 15663 N과 M (9)  (0) 2021.01.28
boj 15656 N과 M (7)  (0) 2021.01.27
boj 15655 N과 M (6)  (0) 2021.01.27
boj 15654 N과 M (5)  (0) 2021.01.27

www.acmicpc.net/problem/15656

 

15656번: N과 M (7)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

N과M 7번째 문제입니다.

이번 문제는 5번째 문제처럼 주어진 배열에서 M개를 고르는데, 같은 수를 골라도 되는 문제입니다.

 

중복이 가능하기 때문에 방문체크는 하지않고 0~N-1까지 접근하시면 됩니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int list[], ans[];
    static int N, M;
 
    static void dfs(int cnt) {
        if (cnt == M) {
            for (int i = 0; i < M; i++) {
                sb.append(ans[i] + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = 0; i < N; i++) {
            int x = list[i];
 
            ans[cnt] = x;
            dfs(cnt + 1);
            ans[cnt] = 0;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[N];
        ans = new int[M];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0);
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 15663 N과 M (9)  (0) 2021.01.28
boj 15657 N과 M (8)  (0) 2021.01.27
boj 15655 N과 M (6)  (0) 2021.01.27
boj 15654 N과 M (5)  (0) 2021.01.27
boj 15652 N 과 M (4)  (0) 2021.01.26

www.acmicpc.net/problem/15655

 

15655번: N과 M (6)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

N과M 6번째 문제입니다.

이번에도 주어진 배열에서 M개이 수열을 고르면 되는데 오름차순으로 골라야한다는 차이가 있습니다.

 

5번째 문제와 마찬가지로 배열이 정렬이 안되어있기 때문에 정렬부터 해준 후에 백트래킹을 돌립니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int list[], ans[];
    static boolean visit[] = new boolean[10001];
    static int N, M;
 
    static void dfs(int idx, int cnt) {
        if (cnt == M) {
            for (int i = 0; i < M; i++) {
                sb.append(ans[i] + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = idx; i < N; i++) {
            int x = list[i];
 
            if (visit[x])
                continue;
 
            visit[x] = true;
            ans[cnt] = x;
            dfs(i + 1, cnt + 1);
            ans[cnt] = 0;
            visit[x] = false;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[N];
        ans = new int[M];
        
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0, 0);
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 15657 N과 M (8)  (0) 2021.01.27
boj 15656 N과 M (7)  (0) 2021.01.27
boj 15654 N과 M (5)  (0) 2021.01.27
boj 15652 N 과 M (4)  (0) 2021.01.26
boj 15651 N과 M (3)  (0) 2021.01.26

www.acmicpc.net/problem/15654

 

15654번: N과 M (5)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

N과M 5번째 문제입니다.

 

다른 문제와는 다르게 주어진 배열에서 길이가 M인 수열을 구하는 문제입니다.

 

배열이 정렬되어있지 않은 상태로 주어지니 정렬부터 하고 dfs를 돌려주면 되겠습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int list[], ans[];
    static boolean visit[] = new boolean[10001];
    static int N, M;
 
    static void dfs(int cnt) {
        if (cnt == M) {
            for (int i = 0; i < M; i++) {
                sb.append(ans[i] + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = 0; i < N; i++) {
            int x = list[i];
            if (visit[x])
                continue;
 
            visit[x] = true;
            ans[cnt] = x;
            dfs(cnt + 1);
            ans[cnt] = 0;
            visit[x] = false;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[N];
        ans = new int[M];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0);
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 15656 N과 M (7)  (0) 2021.01.27
boj 15655 N과 M (6)  (0) 2021.01.27
boj 15652 N 과 M (4)  (0) 2021.01.26
boj 15651 N과 M (3)  (0) 2021.01.26
boj 15650 N 과 M (2)  (0) 2021.01.26

www.acmicpc.net/problem/1002

 

1002번: 터렛

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

www.acmicpc.net

이 문제는 두 사람의 위치와 그 위치에서 각각 보이는 적까지의 거리가 주어지며 수학적 지식이 필요한 문제입니다.

저는 원의 반지름과 두 점 사이의 거리를 이용하여 해결하였습니다.

 

A의 좌표가 주어지고, A가 계산한 적까지의 거리를 반지름이라고 생각하시면 됩니다.

B도 같은 방법으로 하면 두개의 원이 그려집니다.

그러면 이 문제는 두 원의 접점의 갯수를 구하는 문제가 됩니다.

두 원이 접하는 경우는 두가지인데 외접과 내접 모두 생각을 해야합니다.

 

두 점 사이의 거리 = d

A의 반지름 = r1 (더 짧은 반지름)

B의 반지름 = r2 (더 긴 반지름)

라고 하였을 때

 

d > r1 + r2    ->    접하지 않으므로 0개

d == r1 + r2  ->    접점이 1개(외접)

d < r1 + r2    ->    접점이 2개이거나 내접여부 확인

 

d + r1 == r2  ->    접점이 1개(내접)

d + r1 > r2    ->    접점이 2개

나머지 -> 0

 

으로 계산하였습니다.

 

 

 
 
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
 
    static class Circle {
        double x;
        double y;
        double r;
    }
 
    static Circle A, B;
    static double d;
    static int ans;
 
    static void swap() {
        Circle tmp = A;
        A = B;
        B = tmp;
    }
 
    static void func() {
        if (A.r > B.r) {
            swap();
        }
 
        if (A.x == B.x && A.y == B.y && A.r == B.r)
            ans = -1;
        else if (d == A.r + B.r)
            ans = 1;
        else if (d > A.r + B.r)
            ans = 0;
        else {
            if (d + A.r == B.r)
                ans = 1;
            else if (d + A.r > B.r)
                ans = 2;
            else
                ans = 0;
        }
    }
 
    static void print() {
        sb.append(ans + "\n");
        ans = 0;
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        A.x = Double.parseDouble(st.nextToken());
        A.y = Double.parseDouble(st.nextToken());
        A.r = Double.parseDouble(st.nextToken());
        
        B.x = Double.parseDouble(st.nextToken());
        B.y = Double.parseDouble(st.nextToken());
        B.r = Double.parseDouble(st.nextToken());
        d = Math.sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            A = new Circle();
            B = new Circle();
            input();
            func();
            print();
        }
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > Math' 카테고리의 다른 글

boj 13136 Do Not Touch Anything  (0) 2022.10.25
boj 1837 암호제작  (0) 2021.02.04
boj 15740 A+B - 9  (0) 2021.01.31

www.acmicpc.net/problem/9657

 

9657번: 돌 게임 3

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

www.acmicpc.net

dp로 해결할 수 있는 문제입니다.

 

상근이가 게임을 먼저 시작하고, 한 번에 가져갈 수 있는 돌의 갯수는 1개, 3개, 4개 입니다.

 

마지막에 돌은 가져간 사람은 승리하므로 dp[1] = true, dp[3] = true, dp[4] = true를 초기값으로 잡습니다.

그리고 dp[5]부터 dp[N]까지 반복문을 돌립니다.

 

여기서 i번째에서 돌을 가져갔을 때 남아있는 돌의 갯수에 따른 승패여부를 확인해야합니다.

돌을 1개 가져갔을 때 i - 1,

돌을 3개 가져갔을 때 i - 3,

돌을 4개 가져갔을 때 i - 4이므로

dp[i - 1], dp[i - 3], dp[i - 4]의 상황을 모두 체크해야합니다.

 

두 플레이어는 이기기 위해 최선을 다한다고 생각하고,

돌을 가져갔을 때 dp[i - 1], dp[i - 3], dp[i - 4] 모두가 true면 상대방이 무조건 이기는 경우이므로 false입니다.

반대로 dp[i - 1], dp[i - 3], dp[i - 4] 중 하나라도 false인 경우가 있으면 그 경우를 선택하면 무조건 이기므로 true입니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static boolean dp[] = new boolean[1001];
    static int N;
 
    static void func() {
        dp[1] = true;
        dp[3] = true;
        dp[4] = true;
        for (int i = 5; i <= N; i++) {
            if (dp[i - 1] && dp[i - 3] && dp[i - 4])
                dp[i] = false;
            else
                dp[i] = true;
        }
    }
    
    static void print() {
        if(dp[N])
            System.out.println("SK");
        else
            System.out.println("CY");
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}
 cs

'algorithm > dp' 카테고리의 다른 글

boj 5573 산책  (0) 2021.02.04
boj 17528 Two Machines  (0) 2021.01.28
boj 2096 내려가기  (0) 2021.01.22
boj 1103 게임  (0) 2021.01.22
boj 12852 1로 만들기 2  (0) 2021.01.22

www.acmicpc.net/problem/4889

 

4889번: 안정적인 문자열

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우

www.acmicpc.net

괄호가 주어지는대로 그리디하게 해결할 수 있는 문제입니다.

 

'{'가 주어지면 스택에 바로 push합니다.

'}'일때 스택이 비어있으면 ans에 1을 더하고 방향을 바꿔 '{'로 스택에 push합니다.

스택이 비어있지 않으면 pop을 해주면 됩니다.

 

이 과정을 반복한 후에 스택이 비어있지 않으면 '{'이 짝수개 남아있다는 말이 됩니다.

그래서 마지막에 s.size()/2를 더해주고 출력합니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static Stack<Character> s = new Stack<>();
    static char ch[];
    static int ans = 0;
 
    static void func() {
        for (char x : ch) {
            if (x == '{') {
                s.push(x);
            } else {
                if (s.isEmpty()) {
                    ans++;
                    s.push('{');
                } else
                    s.pop();
            }
        }
 
        ans += (s.size() / 2);
        sb.append(ans + "\n");
        ans = 0;
        while (!s.isEmpty())
            s.pop();
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        ch = st.nextToken().toCharArray();
    }
 
    public static void main(String[] args) throws Exception {
        for (int T = 1;; T++) {
            input();
            if (ch[0] == '-')
                break;
 
            sb.append(T + ". ");
            func();
        }
        
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 11279 최대 힙  (0) 2021.01.31
boj 1927 최소 힙  (0) 2021.01.31
boj 2504 괄호의 값  (0) 2021.01.26
boj 6198 옥상 정원 꾸미기  (0) 2021.01.26
boj 1874 수택 수열  (0) 2021.01.25

+ Recent posts

티스토리툴바