각각의 거리에 대한 최단거리를 구하는 문제입니다. a, b, c 있다면 a -> b a -> c b -> a b -> c c -> a c -> b 를 구하는 문제입니다. 모든 노드쌍에 대한 최단거리를 구할 때는 플로이드-워셜 알고리즘을 사용합니다. 반복문을 3번 이용해서 구현할 수 있습니다. #include #include #define INF 987654321 using namespace std; int d[101][101]; int n, m; void Init() { for (int i = 1; i > x; cin >> y; cin >> c; if (d[x][y] > c) { d[x][y] = c; } } Floyd(); for (int i = 1; i

2^n으로 이루어진 사각형에서 (x, y) 위치에 몇번째에 도착하는지 묻는 문제입니다. 순서는 위의 그림과 같이 Z모양으로 움직입니다. Z라는 모양을 작은 것에서 점점 크게 그리는 반복작업이 있기때문에 분할정복 기법을 사용했습니다. 재귀함수를 통해서 x, y가 찾는 위치의 값과 같아질때까지 반복을 합니다. 길이가 더 이상 분할할수 없으면 +1을 해줍니다. 탐색 중인 사분면에 찾는 위치가 있을 수 없으면 그 사분면의 크기만큼 +를 해줍니다. #include #include using namespace std; int n, r, c; int result; void recursion(int x, int y, int len) { if (y == r && x == c) { //찾는 좌표의 결과값 출력 cout c..

n*m크기의 초콜릿을 n*m개가 될때까지 쪼개는 문제입니다. 예를들어 2*2 = 4 4조각의 초콜릿을 반으로 자르면 2조각이 2개 생길것입니다. ( 4 ) -> ( 2 2 ) 거기서 2조각 짜리를 한번 자르면 1조각이 2개 2조각이 1개가 생깁니다. ( 2 2 ) -> ( 1 1 2 ) 마저 2조각을 한번 더 자르면 1조각이 4개가 됩니다. ( 1 1 2 ) -> ( 1 1 1 1 ) 여기서 2조각을 한조각으로 자르는 과정을 2번 반복하게 됩니다. 조각 수가 커진다면 더 많은 반복이 일어나게 될것입니다. 이를 줄이기 위해 다이나믹 프로그래밍 기법을 사용해서 문제를 풀었습니다. memo라는 배열에 몇조각이였을때 몇번 나눠야된다는 것이 입력이 되면 그 후로는 같은 조각 수가 나왔을때 이미 나온 결과를 가져오..

0~9까지의 플라스틱 숫자 세트가 있습니다. 이를 이용해서 방 번호 N을 만들려고 합니다. 플라스틱 숫자 세트를 몇개 사용해서 방 번호를 만들 수 있는지 찾는 문제입니다. 6과 9는 뒤집어서 사용할 수 있습니다. 먼저 arr[]배열에 숫자가 사용 될때마다 추가를 해줍니다. 그리고 arr[9]는 arr[6]을 더해준 뒤 2로 나눕니다. arr[0]~arr[9]에서 가장 높은 값이 나온 만큼 세트가 있다고 판단할 수 있습니다. #include using namespace std; int main(int argc, char * argv[]) { int arr[10] = { 0,}; int num; int index; int max=0; cin >> num; do { index = num % 10; num /=..

k층에 n호에는 몇명이 살아야하는지 출력을 해야합니다. k층에 n호는 k-1층에 1~n호의 사람들의 합만큼 살아야합니다. ... 2층 1 4 10 20 ... 1층 1 3 6 10 ... 0층 1 2 3 4 ... 1호 2호 3호 4호 house[]에는 0층 1호~14호까지의 인원이 입력되어 있습니다. ex) 1, 2, 3, 4 .... 12, 13, 14 그리고 찾고자 하는 k층이 될때까지 house[]에는 그다음 층의 값들로 업데이트를 해주도록 하였습니다. #include using namespace std; int house[14]; void init() { for (int i = 0; i < 14; ++i) { house[i] = i + 1; } } int main(int argc, char * ..

세자리 수를 두개 받은 후 각각 1의 자리와 100의 자리를 바꾸었을 때 높은 숫자를 출력하면 됩니다. 734 -> 437 893 -> 398 437이 크므로 437을 출력합니다. a와 b에 바뀐 값들을 넣어준 후 비교한 후 출력해서 문제를 풀었습니다. #include using namespace std; int main(int argc, char *argv[]) { int a, b; cin >> a; cin >> b; a = a/100 + ((a-a/100*100)/10)*10 + (a-a/10*10)*100; b = b/100 + ((b-b/100*100)/10)*10 + (b-b/10*10)*100; if(a>b){ cout

0부터 셀프넘버들을 확인합니다. 셀프넘버인 것들은 배열 a[셀프넘버] 에 NULL을 대입해줍니다. 그리고 모든 과정이 끝난 후 NULL이 아닌 a의 배열안의 값들만 출력해줍니다. #include using namespace std; int main(int argc, char *argv[]) { int a[10000]; int q=0, w=0, e=0, r=0; int result = 0; int i=0; for(i=0;i= 1){ w = (i - q*1000)/100; } if(i/10 >= 1){ e = (i - q*1000 - w*100)/10; } r = i - q*1000 - w*100 - e*10; result = i + q + w + e + r; if(result

1의 자리 수와 그 전에 더했던 숫자를 계속해서 더하면서 원래 숫자가 나올때까지 몇번 반복해야하는지 찾는 문제입니다. 26의 경우 2 + 6 = 8 68 6 + 8 = 14 84 8 + 4 = 12 42 4 + 2 = 6 26 4번의 순환을 통해 찾았습니다. a = 10의 자리 수 b = 1의 자리 수 c = a+b를 더한 후 1의 자리 수 d = 합쳐진 수 6 + 8 = 14 84 를 예로 들면 a = 6 b = 8 c = 4 d = 84 입니다. #include using namespace std; int main(int argc, char * argv[]) { int x; int a, b, c, d; int count = 0; cin >> x; d = x; while (d != x || count ..