<링크>

https://www.acmicpc.net/problem/15686


<소스코드>

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
#include<cstdio>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
typedef pair<int, int> P;
vector<P> h,c,a; // 집, 치킨집, 남겨둘 치킨집
int N, M;
int ans = 1e9;
void check(vector<P> &a)
{
    if (a.size() == 0)
        return;
    int sum = 0;
    for (P i : h)
    {
        int m = 1e9;
        for (P j : a)
            m = min(m, abs(i.first - j.first) + abs(i.second - j.second));
        sum += m;
    }
    ans = min(ans, sum);
}
void recur(int i, int len)
{
    if (len <= M)
        check(a);
    if (i == c.size()||len>M)
        return;
    a.push_back(c[i]);
    recur(i + 1, len + 1);
    a.pop_back();
    recur(i + 1, len);
}
int main()
{
    scanf("%d%d", &N, &M);
    for(int i=0;i<N;++i)
        for (int j = 0; j < N; ++j)
        {
            int n;
            scanf("%d", &n);
            if (n == 1)
                h.push_back({ i,j });
            if (n == 2)
                c.push_back({ i,j });
        }
    recur(0,0);
    printf("%d", ans);
}
 
cs


<풀이>

1. 집 좌표 리스트, 치킨집 좌표 리스트를 미리 준비해둔다.

2. 재귀함수를 이용해서 치킨집 조합을 만든다.

i번째 치킨집을 포함하면 a벡터에넣고 재귀호출, 안하면 a.pop_back()으로 뺀 후 재귀호출하고

현재까지 찍은 치킨집 개수가 M개 이하이면 check()함수에 a벡터를 던져준다.

찍은 치킨집 개수가 M개를 넘어가거나 i가 총 치킨집 개수를 넘어가면 return한다.


3. chek()함수에는 내가 찍은 치킨집들의 좌표가 넘어오기 때문에 집 하나당, 찍힌 치킨집 전부를 보며 최솟값을 찾아 더해준다.

모든 집들에 대해 반복해서 더하면 찍은 치킨집들로 만든 도시의 치킨거리가 나온다.

이 값을 보고 답을 갱신한다.

저작자표시

'알고리즘 풀이 > 브루트 포스' 카테고리의 다른 글

백준 1107 리모컨  (2) 2018.07.26
KOITP 고장난시계  (0) 2018.07.23
백준 1421 나무꾼 이다솜 ::들짐승  (0) 2018.07.22
백준 14888 연산자 끼워넣기 :: 들짐승  (0) 2018.07.22

<링크>

https://www.acmicpc.net/problem/1107



지금으로부터 6달 전, 2018년 1월 5일에 풀었었는데 이 때에 비해 실력이 얼마나 늘었는지 궁금해서

똑같은 문제를 또 봤다. 많이 틀리고 개고생했던 기억이 난다.


<2018.01.15 소스코드>

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
77
78
79
80
81
82
83
84
85
86
87
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        // 61453
        // 7 8 9
        Scanner in = new Scanner(System.in);
        String num = in.next();
        int channel = Integer.parseInt(num);
 
        int K = in.nextInt();
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < 10; ++i)
            list.add(i);
 
        for (int i = 0; i < K; ++i)
            list.remove(new Integer(in.nextInt()));
        // list정렬
        Collections.sort(list);
        int nogada = Math.abs(channel - 100);
    
        if (K == 10) { // 칠수있는 번호가 하나도없을시 (다고장)
            System.out.println(Math.abs(channel - 100));
            return;
        }
 
        int mini = channel;
        String min = null;
        boolean check1 = false,check2=false;
        while (mini >= 0) {
            min=Integer.toString(mini);    
            if(channel-mini+min.length()>=nogada)
                break;
        
            check1 = true; // 성공했다고 가정
            for (int j = 0; j < min.length(); ++j) {
                int n = min.charAt(j) - '0';
                if (list.indexOf(n) == -1) {
                    check1 = false;
                    break;
                } // 실패
            }
            if (check1 == true)
                break;
            else
                --mini;
        }
        int maxi=channel;
        String max;
        while (true) {
            max=Integer.toString(maxi);    
            if(maxi-channel+max.length()>=nogada)
                break;
            check2 = true; // 성공했다고 가정
            for (int j = 0; j < max.length(); ++j) {
                int n = max.charAt(j) - '0';
                if (list.indexOf(n) == -1) {
                    check2 = false;
                    break;
                } // 실패
            }
            if (check2 == true)
                break;
            else
                ++maxi;
        }
        mini=channel-mini+min.length();
        maxi=maxi-channel+max.length();
        
        int result=nogada;
        if(maxi<result && check2){
            result=maxi;
        }
        if(mini<result && check1){
            result=mini;
        }
        System.out.println(result);
        
        // 만들수있는숫자 i가 나옴
 
    }
}
 
cs


<풀이>

뭐저렇게 복잡해보이는지 잘 모르겠다. 꼴보기 싫어서 그냥 새로 풀었다.




<2018.07.26 소스코드-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
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
#include<vector>
#include<math.h>
using namespace std;
vector<int> v;
int seq[6];
int X[10];
int ans, N, M;
void check();
void dfs(int);
int main()
{
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; ++i)
    {
        int n;
        scanf("%d", &n);
        X[n] = 1; // 1고장난애들
    }
    ans = abs(N - 100);
    v.push_back(0); //0은 무조건 추가, 자리수관리용
    for (int i = 1; i < 10; ++i)
        if (!X[i])
            v.push_back(i); //누를수있는 버튼을 벡터에 추가
    dfs(0);
    printf("%d",ans);
}
void dfs(int len)
{
    if (len == 6)
    {
        check();
        return;
    }
    for (int i = 0; i < v.size(); ++i)
    {
        seq[len] = v[i];    
        dfs(len + 1);
    }
}
void check()
{
    int i = 0;
    int cnt = 6;
    while (i < 5 && seq[i] == 0) //앞에 붙은 0들을 제거
    {
        ++i;
        --cnt;
    }
    int channel = 0;
    while(i<6)
    {
        if (seq[i] == 0 && X[0]) //앞의 0을 다 제거했으므로 이제 사이에 나오는 0은 0버튼이 고장났는지 여부에 따라 갈림
            return;
        channel += seq[i] * pow(10, 5 - i);
        ++i;
        
    }
    
    if (abs(N - channel) + cnt < ans)
        ans = abs(N - channel) + cnt;
 
}
cs
<풀이>

리모콘 버튼을 하나 선택하고 다음자리 수를 재귀를 돌렸다. 최대 6자리까지만 했다.

N의 최대입력값이 500000이기 때문에 999900 이상되는 수부터는 +,-를 이용해서 오는건, 100번에서 +,-만 이용해서 오는 것보다 구리기 때문이다.


시간복잡도는 10^6이다.


맨 처음 채널에 100이기 때문에 100에서부터 원하는 채널 N까지 +,-를 이용해 가는 값, 즉 |N-100| 으로 최솟값을 일단 정해놓고 고장이 안난 버튼으로 재귀를 돌다가 depth가 6이 되면 최솟값을 갱신했다.


예를 들어

고장난 번호가 3,4,5,6,7,8,9 일 때 가능한 번호는 0,1,2이고


000000

000001

000002

...

000012

...

222220

...

222222

이렇게 모두 체크해본다.


000012를 체크하면, 앞의 0은 누른 횟수로 치지않고 2번 누른 것으로 한다.


근데 여기서 0 버튼이 고장나면 문제가 발생한다.

고장이 안난 버튼으로만 재귀를 돌렸기 때문에

111111

111112

...

222222 이렇게 체크하게 되는데

그럼 6자리가 아닌 채널들은 체크를 못하게된다.

그래서 0은 무조건 재귀돌릴 때 추가하고,  체크할 때 걸러내게끔 했다

000012 -> 얘는 앞자리채우기로써 0이 들어온거니까 : ㅇㅋ

011012 -> 중간에 유효숫자로써 0이 들어온거니까 : ㄴㄴ



<2018.07.26 소스코드-3>

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
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string>
int check(int);
using namespace std;
int X[10];
int ans, N, M;
int main()
{
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; ++i)
    {
        int n;
        scanf("%d", &n);
        X[n] = 1; //고장난애들
    }
    ans = abs(100 - N);
    for (int i = 0; i <= 1000000; ++i)
    {
        int len = check(i);
        if (len)
            ans = min(abs(N - i) + len, ans);
    }
    printf("%d", ans);
}
int check(int num)
{
    string s=to_string(num);
    int len = s.length();
    for (int i = 0; i < len; ++i)
    {
        if (X[s[i] - '0'])
            return 0;
    }
    return len;
}
cs

<풀이>

새롭게 재귀로 풀고나서 좀 늘었구나 싶었는데 

다른 사람들의 소스코드를 살펴보고나서 깨달음을 얻었다.

그냥 0번부터 100000번까지 for문으로 쫙 돌려보며 

가능한 숫자버튼으로 만들수 있는 채널이면 최솟값을 갱신시키는 방식이다.

코드가 80->60->40 줄로 짧아져서 기쁘긴한데 난 아직 멀었다.


저작자표시

'알고리즘 풀이 > 브루트 포스' 카테고리의 다른 글

백준 15686 치킨배달  (0) 2018.09.30
KOITP 고장난시계  (0) 2018.07.23
백준 1421 나무꾼 이다솜 ::들짐승  (0) 2018.07.22
백준 14888 연산자 끼워넣기 :: 들짐승  (0) 2018.07.22

<링크>

https://koitp.org/problem/SDS_TEST_CLOCK/read/


<소스코드>

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
#include<stdio.h>
int ans=0;
void check(int);
int main()
{
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++t)
    {
        ans = 1439; //23:59
        int a;
        int time = 0;
        for (int i = 27; i >= 0; --i)
        {
            scanf("%d", &a);
            time = time | (a << i);
        }
        check(time);
        for (int i = 27; i >= 0; --i)
        {
            int cVal;
            if (time & (1 << i))
                cVal = (time & ~(1 << i));
            else
                cVal = (time | 1 << i);
            check(cVal);
            for (int j = i - 1; j >= 0; --j)
            {
                int dVal=cVal;
                if (dVal & (1 << j))
                    dVal = (dVal & ~(1 << j));
                else
                    dVal = (dVal | 1 << j);
                check(dVal);
            }
        }
 
        printf("#%d %d %d\n",t,ans/60, ans%60);
    }
 
}
void check(int time)
{
    int res[4] = { 0, };
    for (int i = 21; i >= 0; i -= 7)
    {
        int num = -1;
        switch ((time & (0x7F << i)) >> i)
        {
        case 0x7E:num = 0; break;
        case 0x06:num = 1; break;
        case 0x5B:num = 2; break;
        case 0x4F:num = 3; break;
        case 0x27:num = 4; break;
        case 0x6D:num = 5; break;
        case 0x7D:num = 6; break;
        case 0x46:num = 7; break;
        case 0x7F:num = 8; break;
        case 0x6F:num = 9; break;
 
        default:return; //아무숫자도 해당안하면 그건 ㅄ시계니깐 걍리턴
        }
        res[3 - i / 7] = num;
    }
    int minute = res[0] * 600 + res[1] * 60 + res[2] * 10 + res[3];
    if (minute < ans)
        ans = minute;
}
cs


<풀이>

int변수 하나에 28비트를 다 때려박은 후 쉬프트 연산을 이용해 풀었다.

각 숫자마다 정해진 7비트가 있기 때문에

16진수표시법으로 비트를 나타내었다.


이중 for문을 돌며 2개이하로 고장난 상황을 체크하였다.





저작자표시

'알고리즘 풀이 > 브루트 포스' 카테고리의 다른 글

백준 15686 치킨배달  (0) 2018.09.30
백준 1107 리모컨  (2) 2018.07.26
백준 1421 나무꾼 이다솜 ::들짐승  (0) 2018.07.22
백준 14888 연산자 끼워넣기 :: 들짐승  (0) 2018.07.22

<링크>

https://www.acmicpc.net/problem/1421


<풀이>

길이를 1부터 현재 갖고있는 나무 중 최대값까지 체크하며 얼마를 벌 수 있는지 확인한다.

자르는데 드는 횟수는
나누어 떨어졌을때는 나뉜조각의 개수-1, 나누어 떨어지지 않을 때는 나뉜조각의 개수 자체이다.

또한 주의해야할 점은
자르는 비용이 조각을 팔았을때보다 더 든다면 그 나무는 아예 안팔아버리는 게 맞기 때문에
무조건 sum에 합하면안되고 조건을 따져서 합해야한다. 


<소스코드>

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
#include<stdio.h>
int tree[1001];
int main()
{
    int N, C, W;
    scanf("%d%d%d", &N, &C, &W);
    int max = 0;
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", tree + i);
        if (max < tree[i])
            max = tree[i];
    }
    int res = 0;
    for (int i = 1; i <= max; ++i)
    {
        int sum = 0;
        for (int j = 0; j < N; ++j)
        {
            if (tree[j] >= i) //더 작으면 자를 수도 없고 아예 팔수가없는거니깐 제외
            {
                int piece, div;
                piece = tree[j] / i; // 길이 i에 나올수있는 조각의 수
                if (tree[j] % i == 0)
                    div = tree[j] / i - 1; // 자르는비용
                else
                    div = tree[j] / i;
 
                if (piece * W*i - div * C > 0)
                    sum += piece * W*i - div * C;
            }
        }
        if (sum > res)
        {
            res = sum;
        }
    }
    printf("%d", res);
 
}
cs


저작자표시

'알고리즘 풀이 > 브루트 포스' 카테고리의 다른 글

백준 15686 치킨배달  (0) 2018.09.30
백준 1107 리모컨  (2) 2018.07.26
KOITP 고장난시계  (0) 2018.07.23
백준 14888 연산자 끼워넣기 :: 들짐승  (0) 2018.07.22

<링크>

https://www.acmicpc.net/problem/14888



<소스코드>

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
#include<stdio.h>
int num[11];
int opCnt[4];
int N;
int min=1100000000, max=-1100000000;
void recur(int, int);
int main()
{
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf("%d", num + i);
    for (int i = 0; i < 4; ++i)
        scanf("%d", opCnt + i);
    recur(num[0], 1);
    printf("%d\n%d", max, min);
}
void recur(int res,int k)
{
    if (k == N)
    {
        if (res > max)
            max = res;
        if (res < min)
            min = res;
    }
    for (int i = 0; i < 4; ++i)
    {
        if (opCnt[i])
        {
            --opCnt[i];
            switch (i)
            {
            case 0:recur(res + num[k], k + 1); break;
            case 1:recur(res - num[k], k + 1); break;
            case 2:recur(res*num[k], k + 1); break;
            case 3:recur(res / num[k], k + 1); break;
            }
            ++opCnt[i];
        }
    }
}
cs


<풀이>

opCnt배열에 각 연산자 기호의 개수를 입력받는다.

예를 들어 
+ - * /
2 1 0 1

이라면,

++-/
++/-
+-+/
+-/+
+/+-
+/-+
...
/+-+
/-++

처럼
모든 가능한 연산자 순서를 다 적용시켜서 나오는 결과값을 보면 된다.


순열과 비슷하지만 한 연산자가 여러 개 있을 수 있기 때문에
각각의 연산자 cnt를 감소시키며 dfs를 하고, cnt가 0이 되면 해당 연산자는 다 본 것이기 때문에 넘어간다.
호출되기 직전에 cnt를 감소시켜주고, 호출이 끝나면 다시 cnt를 증가시켜줘야한다. 
이는 순열만들기의 dfs에서 visit를 체크하는 방법과 유사하다. 
자신이 사용했다가 끝나면 다시 원상복귀를 시켜줘야 나중에 사용할 때 문제가 없다.



저작자표시

'알고리즘 풀이 > 브루트 포스' 카테고리의 다른 글

백준 15686 치킨배달  (0) 2018.09.30
백준 1107 리모컨  (2) 2018.07.26
KOITP 고장난시계  (0) 2018.07.23
백준 1421 나무꾼 이다솜 ::들짐승  (0) 2018.07.22

+ Recent posts

티스토리툴바