<링크>

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/9011


<풀이>

내앞에 나보다 작은 수가 몇 개 있는지 주어지면 원래 수열을 찾는다.
맨 뒤부터 참조하면 된다.
맨 뒤에서 9라면 나는 10일 수 밖에 없다.
10
0 0 0 2 0 1 6 7 6 9 

맨뒤부터 숫자 그대로를 index로 사용하고 벡터에서 erase()하였다.
벡터에서 특정 위치의 원소를 erase하면 뒤에 있는 것들이 앞으로 한칸씩 땡겨오기 때문에 사용했다.
v : 1 2 3 4 5 6 7 8 9 10
v[9]=10 ->제거
1 2 3 4 5 6 7 8 9
v[6]=7 ->제거
1 2 3 4 5 6 8 9
v[7]=9 ->제거
1 2 3 4 5 6 8
v[6]=8 -> 제거
1 2 3 4 5 6
...
v[0]=6 ->제거

제거한값들을 거꾸로 나열하면 답이 된다.

IMPOSSIBLE이 뜨는 경우는 잘 모르겠어서 그냥 마지막 예제 입력을 위 과정대로 해봤더니
잘못된 입력이 있으면 접근하고자 하는 index가 현재 남아있는 벡터의 범위를 벗어나게 된다.
그냥 예제 따라해보면 쉽게 풀 수 있다.


<소스코드>

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
#include<stdio.h>
#include<vector>
using namespace std;
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int N;
        scanf("%d", &N);
        vector<int> v;
        for (int i = 1; i <= N; ++i)
            v.push_back(i);
        int seq[101];
        int res[101];
        for (int i = 0; i < N; ++i)
            scanf("%d", seq + i);
        int check=1;
        for (int i = N - 1; i >= 0; --i)
        {
            int to = seq[i];
            if (to >= v.size())
            {
                printf("IMPOSSIBLE");
                check = 0;
                break;
            }
            res[i] = v[to];
            v.erase(v.begin() + to);
        }
        if (check)
            for (int i = 0; i < N; ++i)
                printf("%d ", res[i]);
        printf("\n");
 
 
    }
}
cs


저작자표시

'알고리즘 풀이 > 기타' 카테고리의 다른 글

백준 10973 이전 순열  (0) 2018.07.24
백준 10972 다음 순열  (1) 2018.07.24
백준 2725 보이는 점의 개수:: 들짐승  (0) 2018.07.22
백준 8982 수족관1 :: 들짐승  (0) 2018.07.22
백준 5624 좋은 수 :: 들짐승  (0) 2018.07.22

<링크>

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


<풀이>

모든 노드를 시작점으로 잡아 dfs를 한번씩 해준다.
dfs를 재귀 호출할 때마다 노드 간의 거리를 계속 더해서 인자로 넘기면, 시작점부터 현재노드까지의 거리가 된다.

dist[i][j] = i부터 j까지의 거리


<소스코드>

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
#include<stdio.h>
#include<vector>
using namespace std;
vector<pair<int,int>> adj[1001];
int isVisited[1001];
int dist[1001][1001];
void dfs(int, int, int);
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    for(int n=0;n<N-1;++n)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    for (int i = 1; i <= N; ++i)
    {
        isVisited[i] = 1;
        dfs(i, i,0);
        isVisited[i] = 0;
    }
    while (M--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", dist[a][b]);
    }
}
void dfs(int start,int i,int len)
{
    dist[start][i] = len;
    int size = adj[i].size();
    for (int j = 0; j < size; ++j)
    {
        int toi = adj[i][j].first;
        int cost = adj[i][j].second;
        if (!isVisited[toi])
        {
            isVisited[toi] = 1;
            dfs(start, toi, len + cost);
            isVisited[toi] = 0;
        }
    }
}
cs


저작자표시

'알고리즘 풀이 > DFS' 카테고리의 다른 글

백준 10819 차이를 최대로  (0) 2018.07.27
백준 10974 모든 순열  (2) 2018.07.24
KOITP 큰수만들기  (0) 2018.07.23
백준 11724 연결 요소의 개수 :: 들짐승  (0) 2018.07.23
백준 11403 경로 찾기 :: 들짐승  (0) 2018.07.23

<링크>

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


<특이점>

테스트케이스 수가 따로 없을 때는 WHILE문 안에 입력함수를 넣으면 된다.


<cin으로 공백 무시하고 한 줄 싹다 받는법>

1. char 배열에 받기
cin.getline(배열이름, 최대길이);
최대길이는 그냥 배열 사이즈랑 똑같이

2. string 변수에 받기
getline(cin,string이름);
길이제한 없음


<소스코드>

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
#include<stdio.h>
#include<string.h>
int main()
{
    char buf[200];
    while (fgets(buf, sizeof(buf), stdin)!=NULL)
    {
        buf[strlen(buf) - 1] = 0;
        int a=0, b=0, c=0, d=0;
        int len = strlen(buf);
        for (int i = 0; i < len; ++i)
        {
            if (buf[i] >= 'A' && buf[i] <= 'Z')
                ++a;
            else if (buf[i] >= 'a' && buf[i] <= 'z')
                ++b;
            else if (buf[i] >= '0' && buf[i] <= '9')
                ++c;
            else
                ++d;
        }
        printf("%d %d %d %d\n", b, a, c, d);
    }
 
}
cs


저작자표시

'알고리즘 풀이 > 라이브러리' 카테고리의 다른 글

백준 1302 베스트셀러 :: 들짐승  (0) 2018.07.22
백준 11580 Footprint :: 들짐승  (0) 2018.07.22

<링크>

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



<풀이>


1. 배열에 수평선의 각 index마다 총 깊이가 몇인지를 기록한다.


2. 구멍이 몇 열에 위치했는지 벡터에 집어넣는다.

깊이는 각 열마다의 총깊이이고, 시작깊이는 물이 시작되는 깊이이다. 맨 처음에는 물이 꽉차있는 상태이기 때문에 시작깊이는 모두 0이다.
구멍이 있는 열은 1, 3이다. 연속된 같은 깊이에서의 구멍은 여러 개가 있던, 어느 곳에 있던 상관없이 하나로 취급해도 된다. 따라서 그냥 3열이라고 했다. 4열에 구멍이 있다해도 똑같다.

3. 구멍이 있으면 그 열의 시작깊이는 총깊이와 같게 된다. 

적어도 해당구멍의 열의 물은 다 빠져나가기 때문이다. 그후 좌측, 우측으로 쭉 훑는데 어떻게 훑냐면


1
2
3
4
5
6
7
8
9
10
11
int cur = hall[i];
int h = depth[cur];
startDepth[cur] = h; //현재 구멍자리
//왼쪽 ㄱㄱ
for (int j = cur - 1; j >= 0; --j)
{
    if (h > depth[j])
        h = depth[j];
    if (startDepth[j] < h)
        startDepth[j] = h;
}
cs

h보다 깊이가 작으면 h를 그 값으로 갱신해준다. 이제 그보다 깊은 높이가 나와도 물을 뺄 수 없기 때문이다.
h보다 시작깊이가 낮으면 물을 뺄 수 있기 때문에 해당 열의 시작깊이를 h로 바꿔준다.
우측도 마찬가지로 진행한다.


h는 3으로 시작했고, 우측으로 훑을 때 녹색칸에서 h가 2로 바뀐다.

4. 위 과정들을 모든 구멍에 대해 반복한 후
5. 각 열마다 깊이-시작깊이 값을 모두 더해주면 남은 물의 양이 된다.


저작자표시

'알고리즘 풀이 > 기타' 카테고리의 다른 글

백준 10973 이전 순열  (0) 2018.07.24
백준 10972 다음 순열  (1) 2018.07.24
백준 2725 보이는 점의 개수:: 들짐승  (0) 2018.07.22
백준 9011 순서 :: 들짐승  (1) 2018.07.22
백준 5624 좋은 수 :: 들짐승  (0) 2018.07.22

+ Recent posts

티스토리툴바