'분류 전체보기' 카테고리의 글 목록 (10 Page)

문제 >> 1225. [S/W 문제해결 기본] 7일차 - 암호생성기

#include 

int main() {

	int tc=1;

	
	while (tc <= 10) {
		int pw[8] = { 0 ,};
		bool flag = false;
		scanf("%d", &tc);

		for (int i = 0; i < 8; i++) {
			scanf("%d", &pw[i]);
		}

		while (true) {

			for (int i = 1; i <= 5; i++) { //1 사이클
				int tmp = pw[0] - i;
				if (tmp <= 0) {
					tmp = 0;
					flag = true; // pw 완성
				}
				for (int j = 0; j < 7; j++) { //한칸씩 당기기
					pw[j] = pw[j + 1];
				}
				pw[7] = tmp;
				if (flag) break;
			}

			if (flag) break;

		}
		
		printf("#%d ", tc);
		for (int i = 0; i < 8; i++) {
			printf("%d ", pw[i]);
		}
		printf("\n");
		tc++;

	}


	return 0;
}

문제에 주어진 대로 배열의 [0]번째 요소에서 해당 값만큼 감소시킨 후 tmp에 담아주고,
[1]번째 요소부터 마지막요소까지 한칸씩 당겨준 다음에 계산한 값을 맨뒤로 삽입해 주는 것을 반복했다.
testcase 개수는 10개로 제한.
input 파일에 값들이 testcase랑 배열 값이랑 공백으로 구분되어 있지 않으니 입력할 때 주의할 것.

저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기 (0)	2019.01.15
[BOJ] 1018 : 체스판 다시 칠하기 (0)	2019.01.11
1206. [S/W 문제해결 기본] 1일차 - View (0)	2019.01.11
[BOJ] 15686 : 치킨배달 (1)	2019.01.08
Baby-gin (0)	2019.01.08

1234

저작자표시

'Diary' 카테고리의 다른 글

역삼 민들레떡볶이 (3)	2019.01.30
역삼 호타루 (2)	2019.01.25
역삼 전봇대 (2)	2019.01.23
역삼 광역시맥주8220 (1)	2019.01.12
사이트맵 (0)	2019.01.08

sitemap.xml

저작자표시

'Diary' 카테고리의 다른 글

역삼 민들레떡볶이 (3)	2019.01.30
역삼 호타루 (2)	2019.01.25
역삼 전봇대 (2)	2019.01.23
역삼 광역시맥주8220 (1)	2019.01.12
유스토리 블로그 테스트 (1)	2019.01.09

1. 문제

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

2. 접근법

먼저 치킨집 중 M개를 선택하고 최소 치킨 거리를 구하는 문제이다.
치킨집을 선택하는 방법이 핵심인것같다.

처음에 계속 시간초과가 났는데, 자신이 선택한 인덱스 이후에서 다음 치킨집을 선택하도록 코드를 변경한 후 해결할 수 있었다.

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
92
93
94
// 0: 빈칸, 1: 집, 2: 치킨집
 
#include <iostream>
#include <vector>
using namespace std;
 
int n, m;
int chicken_index = 0;
int home_index = 0;
int origin_map[52][52] = { 0 };
int map[52][52] = { 0 };
int final_d = 987654321;
pair<int, int> chicken[14];
pair<int, int> selected[14];
vector<pair<int, int>> home;
bool visited[14] = {false};
 
int abs(int a) {
    return a>0 ? a : -1 * a;
}
 
int distance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}
 
 
 
int solve() {
    
    int total_d = 0;
    
    for (int i = 0;i < home.size();i++) {
        int min_d = 987654321;
        for (int k = 0; k < m; k++) {
            int d = distance(home[i].first, home[i].second, selected[k].first, selected[k].second);
            min_d = min_d > d ? d : min_d;
        }
        total_d += min_d;
    }
    
    /*
     for (int i = 1;i <= n;i++) {
     for (int j = 1;j <= n;j++) {
     if (map[i][j] != 1)continue;
     
     int min_d = 987654321;
     for (int k = 0;k<m;k++) {
     int d = distance(i, j, selected[k].first, selected[k].second);
     min_d = min_d > d ? d : min_d;
     }
     total_d += min_d;
     }
     }*/
    
    return total_d;
}
 
void select(int len, int k) {
    if (len == m) {
        int d = solve();
        final_d = final_d > d ? d : final_d;
        return;
    }
    for (int i = k;i<chicken_index;i++) {
        
            selected[len] = chicken[i];
            select(len + 1, i+1);
        
        
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 2) {//치킨집 위치 저장
                chicken[chicken_index] = make_pair(i, j);
                chicken_index++;
            }
            else if (map[i][j] == 1) {//집 위치 저장
                home.push_back({i,j});
            }
        }
    }
    
    select(0,0);
    
    printf("%d\n", final_d);
    
    return 0;
}
 
Colored by Color Scripter
cs

저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기 (0)	2019.01.15
[BOJ] 1018 : 체스판 다시 칠하기 (0)	2019.01.11
1206. [S/W 문제해결 기본] 1일차 - View (0)	2019.01.11
1225. [S/W 문제해결 기본] 7일차 - 암호생성기 (0)	2019.01.11
Baby-gin (0)	2019.01.08

1. 개념
https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98


2. 기본 문제(BOJ)
https://www.acmicpc.net/problem/1753


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
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
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
 
 
#define INF 987654321
#define MAX_E 300001
 
using namespace std;
 
typedef struct NODE {
    int end;
    int weight;
};
 
int dist[20000] = { 0, };
vector<NODE> map[MAX_E];
 
int start;
 
 
void dijkstra() {
 
    priority_queue <pair<int, int>> pq;
    pq.push({ 0,start }); //시작점 삽입
 
    while (!pq.empty()){//큐가 빌때까지 반복 
        int now_node = pq.top().second; 
        int cost = -1 * pq.top().first;
        pq.pop(); //제일 우선순위 높은 ... (?) 노드 삭제
 
        for (int k = 0; k < map[now_node].size(); k++) { //now_node에 연결된 정점 체크
        
            int new_val = dist[now_node] + map[now_node][k].weight; 
            int before_val = dist[map[now_node][k].end];
 
            if (new_val < before_val) {
                dist[map[now_node][k].end] = new_val;
                pq.push({ -1 * new_val , map[now_node][k].end });
            } // 간선 weight 갱신
            
 
        }
    }
 
}
 
int main() {
 
    int v, e; //v:정점 e:간선
    
    int from, to, w;
 
    int i, j;
 
    scanf("%d %d", &v, &e);
    scanf("%d", &start); //시작점
 
    for (i = 1;i <= e;i++) {
        scanf("%d %d %d", &from, &to, &w);
        map[from].push_back(NODE{to,w});
    }
 
    for (i = 1;i <= v;i++) {
        dist[i] = INF;
    }
 
    dist[start] = 0;
 
    dijkstra();
 
 
    for (i = 1;i <= v;i++) {
        if (dist[i] != INF) printf("%d\n", dist[i]);
        else printf("INF\n");
    }
 
    return 0;
}
 
Colored by Color Scripter
cs

처음에 map 벡터에 연결된 정점들과 해당 weight를 저장해준다.

우선순위 큐는 min_heap ! (weight이 작은것부터 방문하는 이유)

* 우선순위 큐는 기본적으로 큰 원소가 pop의 우선순위를 가지기 때문에,

음의 가중치로 바꾸어 우선순위 큐에 넣는다. (-1을 곱하는 이유)

ex) weight이 10, 9, 8 이라는 값이 들어왔다면 우선순위는 1 2 3 이어야함.

저작자표시

'Computer Science > Algorithms' 카테고리의 다른 글

[java] Dijkstra 다익스트라 알고리즘 (0)	2019.02.19
Kruskal 크루스칼 알고리즘 (0)	2019.02.18
DisjointSets (0)	2019.02.18
[java] Insertion Sort 삽입정렬 (0)	2019.01.28
Permutation 순열 (0)	2019.01.17

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    //입력
        
        Scanner sc = new Scanner(System.in); // jdk5 추가됨
        int num = sc.nextInt();
        
        //빠르다
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine(); // 문자열로만 리턴됨, 사용자가 입력한 한 줄을 통째로 문자열로 받아옴.
        s="20";
        int num = Integer.parseInt(s); //숫자로 변경
        //int num = Integer.valueOf(s); //내부적으로  parseInt를 다시 호출.
        s="1 2 3 4 5";
        String[] srr = s.split(" ");
        
        
        
        //출력
        System.out.println(); //느리다. 한번에 묶어서 출력하는 것이 좋다.
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write("abcdefg\n"); //줄 안바꿔줌, \n
Colored by Color Scripter
cs

저작자표시

'Computer Science > Languages' 카테고리의 다른 글

[java] 쓰레드(Thread) (0)	2019.01.24
[java] 예외처리 (2)	2019.01.24
[java] Collection 활용 (0)	2019.01.17
[java] interface (0)	2019.01.16
[Java] final, static (0)	2019.01.16

Baby-Gin Game

- 각 카드는 0에서 9까지의 숫자가 쓰여져 있다.

- 6장의 카드를 받는다.

- 임의의 카드 6장 중, 3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하며, 
  3장의 카드가 동일한 번호를 갖는 경우를 triplet 이라고 한다.

- 6장의 카드가 run과 triplet로만 구성된 경우를 baby-gin으로 부른다.

- 901은 run이 아니다.

예시 )
- 667767은 두 개의 triplet이므로 baby-gin이다. (666,777)
- 054060은 한 개의 run과 한 개의 triplet이므로 역시 baby-gin이다. (456, 000)
- 101123은 한 개의 triplet가 존재하나, 023이 run이 아니므로 baby-gin이 아니다.
  (123을 run으로 사용하더라도 011이 run이나 triplet가 아님)



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

 
import java.util.Arrays;
 
public class BabyJin {
    public static void main(String[] args) {
        int[] arr= {1,0,3,2,3,3,};
        int[] cnt = new int[10];
 
        
        for(int i=0;i<arr.length;i++) {
            cnt[arr[i]]++;
        } //카운팅 소트
        
        
        for(int i=0;i<cnt.length;i++) { //트리플
            if(cnt[i]>=3) {
                System.out.println("Triplet");
                cnt[i]-=3;
            } 
            
            if(i-1>=0 && i+1<cnt.length) { //
                if(cnt[i-1]>0 && cnt[i]>0 && cnt[i+1]>0) {
                    System.out.println("Run");
                    cnt[i-1]--;
                    cnt[i]--;
                    cnt[i+1]--;
                }
            }
        }
        
        for(int i=0;i<cnt.length;i++) {
            if(cnt[i]!=0) return;
        }
        System.out.println("Baby-gin");
    }
}
 
Colored by Color Scripter
cs

'Algorithm Problem Solving' 카테고리의 다른 글

1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기 (0)	2019.01.15
[BOJ] 1018 : 체스판 다시 칠하기 (0)	2019.01.11
1206. [S/W 문제해결 기본] 1일차 - View (0)	2019.01.11
1225. [S/W 문제해결 기본] 7일차 - 암호생성기 (0)	2019.01.11
[BOJ] 15686 : 치킨배달 (1)	2019.01.08

Youth-tory 유스토리