반응형

문제출처

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


문제풀이는 생략하겠습니다.(if문 사용)


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num, sum=0;
    for(int i=1; i<=5; i++) {
        cin>>num;
        if(num<40)  sum+=40;
        else sum+=num;
    }
    cout<<sum/5;
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1697] 숨바꼭질  (0) 2019.01.23
[BOJ 1325] 효율적인 해킹  (0) 2019.01.23
[BOJ 2468] 안전영역  (0) 2019.01.22
[BOJ 2661] 좋은 수열  (0) 2019.01.21
[BOJ 1759] 암호만들기  (0) 2019.01.21
반응형

문제 출처

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


문제풀이

1
2
3
4
5
6
/*
* 모든 높이에 대해 잠기지 않는 안전영역의 갯수를 카운트 해주면 되는 문제
* dfs / bfs로 풀이할 수 있다. 특히 0은 고려하지 않았는데 아래 노트를 보니
* 비가 오지 않는 경우도 있다고 써져있었다.... 하지만 생각해보면 전부 높이가 1인
* 경우가 있을 수 있기 때문에 0도 고려를 해야합니다.
*/
cs


소스코드

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
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100
using namespace std;
int n,result;
int map[MAX][MAX];
bool visit[MAX][MAX];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
void dfs(int x, int y, int height) {
    visit[x][y] = 1;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n)    continue;
        if (map[nx][ny] > height && !visit[nx][ny])    dfs(nx, ny, height);
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    int maxDepth = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            maxDepth = max(maxDepth, map[i][j]);
        }
    }
    for (int height = 0; height <= maxDepth; height++) {
        int safeBlock = 0;
        memset(visit, 0, sizeof(visit));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] > height && !visit[i][j]) {
                    dfs(i, j, height);
                    safeBlock++;
                }
            }
        }
        result = max(result, safeBlock);
    }
    cout << result << endl;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1325] 효율적인 해킹  (0) 2019.01.23
[BOJ 10039] 평균점수  (0) 2019.01.22
[BOJ 2661] 좋은 수열  (0) 2019.01.21
[BOJ 1759] 암호만들기  (0) 2019.01.21
[BOJ 1012] 유기농 배추  (0) 2019.01.21
반응형

문제출처

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


소스코드

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
// BOJ_2661
public class Main {
    private static int n;
    private static boolean stopFlag = false;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dfs(1, "1");
        br.close();
    }
    
    private static boolean isSafe(String str) {
        int len = str.length();
        int repeatCnt = len / 2;
        int start = len - 1;
        int end = len;
        for (int i = 1; i <= repeatCnt; i++) {
            String first = str.substring(start - i, end - i);
            String second = str.substring(start, end);
            if (first.equals(second)) {
                return false;
            }
            start--;
        }
        return true;
    }
 
    private static void dfs(int len, String str) {
        if (stopFlag || !isSafe(str)) {
            return;
        }
        if (len == n) {
            stopFlag = true;
            System.out.println(str);
            return;
        }
        for (int i = 1; i <= 3; i++) {
            dfs(len + 1, str + i);
        }
    }
}
 
 
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 10039] 평균점수  (0) 2019.01.22
[BOJ 2468] 안전영역  (0) 2019.01.22
[BOJ 1759] 암호만들기  (0) 2019.01.21
[BOJ 1012] 유기농 배추  (0) 2019.01.21
[BOJ 1966] 프린터큐  (0) 2019.01.17
반응형

문제출처

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


문제풀이

1
2
3
4
5
6
7
8
9
/*
* 역시 문제를 잘 읽어야 합니다.
* 1. 정렬된 문자열을 선호(정렬필요)
* 2. 최소 한개의 모음과 최소 두개의 자음으로 구성(base case 조건)
* 즉 이 문제는 탐색한 이후 모음 1개이상 자음 2개이상으로 구성된 암호만 출력하면 되며
* 탐색을 하기 전에 정렬을 하고 암호를 만들어 가면 되는 것입니다.
* 자음의 경우를 모두 조건으로 주는 것보다 비교적 수가 적은 모음 조건일때와 아닌경우로 나누었으며
* 모음 조건에 부합하면 모음숫자를 1 증가시켜 재귀적으로 호출하면 되는 문제입니다.
*/
cs


소스코드

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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int l, c;
char ch[16];
void solve(int cur, string password, int consonant, int vowel) {
    if (password.size() == l&& vowel >= 1 && consonant >= 2) {
        cout << password << endl;
        return;
    }
    for (int i = cur; i <= c; i++) {
        if (ch[i] == 'a' || ch[i] == 'e' || ch[i] == 'i' || ch[i] == 'o' || ch[i] == 'u')
            solve(i + 1, password + ch[i], consonant, vowel + 1);
        else
            solve(i + 1, password + ch[i], consonant + 1, vowel);
    }
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> l >> c;
 
    char input;
    for (int i = 0; i < c; i++) cin >> ch[i];
    sort(ch, ch+c+1);
    solve(1, "", 0, 0);
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 2468] 안전영역  (0) 2019.01.22
[BOJ 2661] 좋은 수열  (0) 2019.01.21
[BOJ 1012] 유기농 배추  (0) 2019.01.21
[BOJ 1966] 프린터큐  (0) 2019.01.17
[BOJ 15686] 치킨배달  (0) 2019.01.17
반응형

문제출처

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


문제풀이

1
2
3
4
5
/*
* 어디서 많이 본문제라 생각했는데 단지번호붙이기 문제와 같은 문제이다.
* 단순한 dfs/bfs문제인데 상하좌우를 탐색해가면서 배추가 있는 블럭을 일단 다 탐색하면 
* result에 1을 더해 블럭단위를 출력해준다. 기본 dfs문제입니다.
*/
cs


소스코드

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
#include <iostream>
#include <string.h>
#include <algorithm>
#define MAX 51
 
using namespace std;
int tc, n, m, k;
int map[MAX][MAX];
bool visit[MAX][MAX];
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
 
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m)    continue;
 
        if (map[nx][ny] == 1 && !visit[nx][ny]) {
            visit[nx][ny] = 1;
            dfs(nx, ny);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);    cin.tie(0);
    cin >> tc;
    while (tc--) {
        memset(map, 0, sizeof(map));
        memset(visit, 0, sizeof(visit));
        cin >> n >> m >> k;
        while (k--) {
            int x, y;
            cin >> x >> y;
            map[x][y] = 1;
        }
 
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visit[i][j] && map[i][j] == 1) {
                    dfs(i, j);
                    result++;
                }
            }
        }
        cout << result << endl;
    }
 
    return 0;
}
 
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 2661] 좋은 수열  (0) 2019.01.21
[BOJ 1759] 암호만들기  (0) 2019.01.21
[BOJ 1966] 프린터큐  (0) 2019.01.17
[BOJ 15686] 치킨배달  (0) 2019.01.17
[BOJ 14502] 연구소  (0) 2019.01.16
반응형

문제출처

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


문제풀이

1
2
3
4
5
6
7
8
9
10
11
12
/*
* n이 100밖에 되지 않기 때문에 O(n^2)의 복잡도를 가진다.
* 우선순위큐와 일반큐 두가지를 사용하겠습니다.
*
* 우선순위큐 - 중요도를 저장하며 가장 높은 중요도를 확인
* 일반큐     - 문서 번호를 저장하며 프린터 큐를 구현
* 
* 현재 문서보다 중요도가 높은 문서가 존재한다면! 현재 문서가 가장 중요하지 않다는 말입니다.
* 가장 중요한 것인지 확인할 수는 있겠지만 가장 높은 중요도를 빠르게 확인하기 위해 우선순위큐를 사용하겠습니다.
* 큐 front에 위치하는 문서의 중요도를 확인하고 그 값이 우선순위큐의 front라면 가장 중요한 것이 되겠지요.
* 가장 중요한 문서일 경우 큐와 우선순위 큐에서 모두 pop하고 그렇지 않은 경우라면 큐의 front를 tail로 보냅니다.
*/
cs


소스코드

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 <iostream>
#include <queue>
 
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false);    cin.tie(0);
    int tc, n, m;
    cin >> tc;
    while (tc--) {
        int result = 0;
        queue<pair<int, int> > q;
        priority_queue<int> pq;
        cin >> n >> m;
        int priority;
        for (int i = 0; i < n; i++) {
            cin >> priority;
            q.push(make_pair(priority, i));
            pq.push(priority);
        }
 
        while (!q.empty()) {
            int prior = q.front().first;
            int num = q.front().second;
            q.pop();
            if (pq.top() == prior) {
                result++;
                pq.pop();
                if (num == m)
                    break;
            }
            else q.push(make_pair(prior, num));
        }
        cout << result << endl;
    }
 
    return 0;
}
 
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1759] 암호만들기  (0) 2019.01.21
[BOJ 1012] 유기농 배추  (0) 2019.01.21
[BOJ 15686] 치킨배달  (0) 2019.01.17
[BOJ 14502] 연구소  (0) 2019.01.16
[SWEA 1245] 균형점  (0) 2019.01.15
반응형

문제출처

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
/*
 * 시간복잡도는 계산하지 못하겠다. 최대 13개의 치킨집에서 최대 13개를 고르는 것인데 
 * 순서는 상관이 없으므로 최악의 경우 13C6 일거라 생각된다. 때문에 1초라는 제한시간 내에 전체탐색으로
 * 풀이할 수 있다고 생각되어 dfs로 풀이하였습니다. (혹시 시간복잡도 아시는 분은 댓글 부탁드립니다 ㅜㅜ)
 * 
 * 연구소 문제와 같이 map을 입력받을 때 집과 치킨집의 좌표를 따로 저장했습니다.
 * 이후 dfs를 통해 치킨집을 순서에 관계없이 선택하고 selected 벡터에 저장합니다. 
 * 이 selected벡터의 사이즈가 m인경우 문제에서 주어진 최대 치킨집의 갯수이므로
 * 집과 치킨집의 거리를 계산해서 최소값을 저장해주는 문제입니다.
 * 
 * 여기서 주의할 점을 알아냈습니다. 처음 selected 벡터 이름을 
 * select로 했는데 컴파일 에러가 났습니다. 리눅스 시스템 콜 명령어중 select가 존재해서
 * 전역변수 이름으로는 사용하지 못하는 것같습니다. 
 * 
 * http://man7.org/linux/man-pages/man2/select.2.html 를 참조하세요.
 *
 * 문제를 풀고 지금 리뷰하면서 생각해보니 사실 map을 선언할 필요가 없을 듯합니다.
 * 만약 1을 입력받는다면 house에 push 2를 입력받는다면 chicken에 push해주면 더 깔끔한 코드가 될것같네요.
**/
cs


소스코드

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
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 51
#define INF 0x7fffffff
 
using namespace std;
 
int n, m, result;
int map[MAX][MAX];
vector<pair<int, int> > house, chicken, selected;
 
void dfs(int cur) {
    if (selected.size() == m) {
        int sum = 0;
        for (int i = 0; i < house.size(); i++) {
            int tmp = INF;
            for (int j = 0; j < selected.size(); j++) {
                tmp = min(tmp, abs(house[i].first - selected[j].first) + abs(house[i].second - selected[j].second));
            }
            sum += tmp;
        }
        result = min(result, sum);
        return;
    }
 
    for (int i = cur; i < chicken.size(); i++) {
        selected.push_back(chicken[i]);
        dfs(i + 1);
        selected.pop_back();
    }
}
 
int main(void) {
    scanf("%d %d", &n, &m);
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            scanf("%d", &map[y][x]);
            if (map[y][x] == 1)
                house.push_back(make_pair(y, x));
            else if (map[y][x] == 2)
                chicken.push_back(make_pair(y, x));
        }
    }
    result = INF;
    dfs(0);
    printf("%d\n", result);
 
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1012] 유기농 배추  (0) 2019.01.21
[BOJ 1966] 프린터큐  (0) 2019.01.17
[BOJ 14502] 연구소  (0) 2019.01.16
[SWEA 1245] 균형점  (0) 2019.01.15
[BOJ 1463] 1로 만들기  (0) 2019.01.14
반응형

문제출처

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


문제풀이

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
진짜 시간이 오래걸렸다. 기둥을 세울때 조건을 잘못줘서 자꾸 예외상황이 발생했기 때문이다. 
반복을 줄이려는 생각만 앞서다 정확한 조건을 생각못했다. 
dfs(기둥세우기) 함수에서 x와 y값을 인자로 받아 
x, y부터 for문을 돌리면 된다 생각했는데 x는 가능하지만 y는 불가능 하다. 
왜냐하면 (예제2번의 경우) 최적의 기둥이 (1,5) / (2,4) / (4,4) 인데 
(1,5) 기둥을 세우면 (2,4) 기둥을 세우지 못하기 때문이다. 
dfs를 제대로 이해했다면 이런실수는 없었을텐데 너무 코드만 구조화해서 외워둔 탓인가..ㅠㅠ
결국 0부터 완탐하다가 x만 인자로 넘겨주면 된다는 것을 깨닫고 재제출한 문제...
 
문제풀이는 다음과 같으며 이 문제도 단계를 나눠서 풀이했다. 
 
case 1) 모든 경우에 3개의 기둥을 세운다(dfs)
case 2) 기둥을 세운 map을 복사해둔다. (모든 경우에 대해서 풀어야 하기 때문에 원본이 필요합니다.)
case 3) 복사한 map에 바이러스를 전파시킨다.(bfs)
case 4) 바이러스 전파가 완료되면 0(안전지역)의 갯수를 세어준다. (bfs 아래의 반복문)
 
이과정을 반복하여 풀이하면된다. 바이러스의 초기 위치를 알기위해 
map을 입력받을 때 virus 벡터에 좌표를 넣어주었지만
이과정은 bfs 반복문안에 if(map[i][j] == 2)조건을 주어 위치를 알아낼 수도 있다. 
저는 반복문을 한번 더 돌리기 싫어서 입력할때 받아두었지만 
성능상 그리 크게 차이가 나지는 않을 듯하다.
안전지역의 갯수를 max함수를 통해 큰값을 result에 넣어주고 출력하면 끝!
아! 바이러스를 전파시킬때 bfs를 쓴 이유는 
어디서 bfs는 탐색을 하면서 행위가 이루어질때 좋은 방법이라 주워들었기 때문이다. (정확하지는 않아요 ㅠㅠ)
자세한건 dfs / bfs를 다시 공부하고 문제풀이를 많이해본 후 체득하고 다시 포스팅 하겠습니다.
 
cs


소스코드

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
88
89
90
91
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 8
 
using namespace std;
 
int n,m,result;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
int map[MAX][MAX];
vector<pair<int, int> > virus;
 
void copyMap(int (*src)[MAX], int (*dest)[MAX]) {
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            dest[i][j] = src[i][j];
        }
    }
}
 
void bfs() {
    int copy[MAX][MAX];
    copyMap(map, copy);
 
    queue<pair<int, int> > q;
    for(int i=0; i<virus.size(); i++)
        q.push(virus[i]);
 
    while(!q.empty()) {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
 
        for(int i=0; i<4; i++) {
            int nx=x+dx[i];
            int ny=y+dy[i];
 
            if(nx<0 || ny<0 || nx>=n || ny>=m)    
                continue;
 
            if(copy[nx][ny]==0) {
                copy[nx][ny]=2;
                q.push(make_pair(nx, ny));
            }
        }
    }
    int tmp=0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(copy[i][j]==0)
                tmp++;
        }
    }
 
    result = max(result, tmp);
}
 
void dfs(int x, int cnt) {
    if(cnt==3) {
        bfs();
        return;
    }
 
    for(int i=x; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(map[i][j]==0) {
                map[i][j]=1;
                dfs(i, cnt+1);
                map[i][j]=0;
            }
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin>>map[i][j];
            if(map[i][j]==2)    
                virus.push_back(make_pair(i,j));
        }
    }
 
    dfs(0, 0);
    cout<<result;
    return 0;
}
cs




추가로 생각해본 방법


1
2
3
먼저 입력받을때 0의 갯수를 모두 세어준 뒤
dfs(기둥세우기)에서 3개를 빼준다. 이후 바이러스가 전파될때마다 1씩 빼주면 
0을 카운트 하는 2중 for문을 없앨 수 있다.
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1966] 프린터큐  (0) 2019.01.17
[BOJ 15686] 치킨배달  (0) 2019.01.17
[SWEA 1245] 균형점  (0) 2019.01.15
[BOJ 1463] 1로 만들기  (0) 2019.01.14
[BOJ 14501] 퇴사  (0) 2019.01.14
반응형

문제출처는 링크를 걸어도 따로 로그인해야 하기 때문에 적지 않겠습니다.


이진탐색 이용


소스코드

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
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
struct coordinates {
    int x;
    int y;
};
 
 
coordinates map[11];
 
// 인력 F = G*m1*m2 / (d*d)
// G = 양의 상수
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed;
    cout.precision(10);
    int tc, n;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> map[i].x;
        for (int i = 1; i <= n; i++)
            cin >> map[i].y;
 
        cout << "#" << t << " ";
        for (int i = 1; i < n; i++) {
            double x;
            double left = map[i].x;
            double right = map[i + 1].x;
 
            int cnt = 0;
            while (true) {
                x = (left + right) / 2.0;
                double lf = 0;
                double rf = 0;
                for (int j = 1; j <= i; j++)
                    lf += (map[j].y) / ((map[j].x - x) * (map[j].x - x));
                for(int j=i+1; j<=n; j++)
                    rf += (map[j].y) / ((map[j].x - x) * (map[j].x - x));
 
                if (cnt++ == 100) {
                    cout << x << " ";
                    break;
                }
 
                if (lf > rf)
                    left = x;
                else
                    right = x;
            }
        }
        cout << endl;
    }
    return 0;
}
cs



다른 풀이도 공개해서 보니 이런 풀이도 있었다.

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
#include<stdio.h>
#define E 1e-9
int n, m;
int a[99];
int b[99];
bool less(double x) {
    int i, j, k;
    double sum = 0;
    double cur;
    for (i = 0; i < m; i++) {
        cur = (x - a[i]);
        cur *= cur;
        if (cur < E) return false;
        cur = b[i] / cur;
        sum += cur;
    }
    for (i = m; i < n; i++) {
        cur = (x - a[i]);
        cur *= cur;
        if (cur < E) return true;
        cur = b[i] / cur;
        sum -= cur;
    }
    return sum < 0;
}
 
int main() {
    int t, tv = 0;
    int i, j, k, l;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (i = 0; i < n; i++)scanf("%d", &a[i]);
        for (i = 0; i < n; i++)scanf("%d", &b[i]);
        printf("#%d", ++tv);
        for (m = 1; m < n; m++) {
            double l, r, mid;
            l = a[m - 1];
            r = a[m];
            int cnt = 100;
            while (cnt--) {
                mid = (l + r) / 2;
                if (less(mid))
                    r = mid;
                else
                    l = mid;
            }
            printf(" %.10lf", l);
        }
        printf("\n");
    }
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 15686] 치킨배달  (0) 2019.01.17
[BOJ 14502] 연구소  (0) 2019.01.16
[BOJ 1463] 1로 만들기  (0) 2019.01.14
[BOJ 14501] 퇴사  (0) 2019.01.14
[BOJ 1182] 부분집합의 합  (0) 2019.01.14
반응형

문제출처

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


풀이과정

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * DP문제이다. N이 10^6까지 범위가 주어지기 때문에 전체탐색을 힘들것이라 판단되었다.
 * DP문제에서 가장중요한 점화식은 조금만 생각하면 유추해 낼 수 있다.
 * 연산의 최소값을 출력하기 때문에 일반적으로 n번 연산한 횟수는 n-1번 연산의 최솟값 +1임을 의미한다.
 * 이를 점화식으로 나타내면
 * case 1)
 * dp[n] = min(dp[n/3] + 1, dp[n-1] + 1)
 * case 2)
 * dp[n] = min(dp[n/2] + 1, dp[n-1] + 1)
 * case 3)
 * dp[n] = dp[n-1] + 1
 *
 */
cs



소스코드

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static final int MAX = 1000001;
    public static void main(String[] args) throws Exception {
        int n;
        int[] dp = new int[MAX];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(br.readLine());
 
        // 1일때는 연산횟수가 없다.
        dp[1]=0;
        for(int i=2; i<=n; i++) {
            if(i%3==0)
                dp[i]=Math.min(dp[i/3]+1, dp[i-1]+1);
            else if(i%2==0)
                dp[i]=Math.min(dp[i/2]+1, dp[i-1]+1);
            else
                dp[i]=dp[i-1]+1;
        }
 
        System.out.println(dp[n]);
 
    }
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 14502] 연구소  (0) 2019.01.16
[SWEA 1245] 균형점  (0) 2019.01.15
[BOJ 14501] 퇴사  (0) 2019.01.14
[BOJ 1182] 부분집합의 합  (0) 2019.01.14
[BOJ 1543] 문서 검색  (0) 2019.01.08

+ Recent posts

티스토리툴바