U E D R , A S I H C RSS

1R/2016_09_23

Difference between r1.5 and the current

@@ -83,7 +83,71 @@
}}}

== 곽정흠 ==
{{{
#include <stdio.h>
#define MAX_QUEUE 100000
#define MAX_NODE 100001
int distance[MAX_NODE];
int queue[MAX_QUEUE];
int first = 0, last = 0;
 
void add(int tmp) {
if (last == MAX_QUEUE) {
last = 0;
queue[last++] = tmp;
}
else {
queue[last++] = tmp;
}
}
int delete(void) {
if (first == MAX_QUEUE - 1) {
first = 0;
return queue[MAX_QUEUE-1];
}
else {
return queue[first++];
}
}
int bnf(int n, int k) {
int tmp = delete();
if (tmp == k) {
return 1;
}
if (tmp * 2 <= k+1) {
if (distance[tmp * 2] > distance[tmp] + 1) {
distance[tmp * 2] = distance[tmp] + 1;
add(tmp * 2);
}
}
if (distance[tmp + 1] > distance[tmp] + 1) {
distance[tmp +1] = distance[tmp] + 1;
add(tmp + 1);
}
if (tmp - 1 >= 0&&distance[tmp-1]>distance[tmp]+1) {
distance[tmp -1] = distance[tmp] + 1;
add(tmp - 1);
}
return 0;
}

int main() {
int n, k;
for (int i = 0; i < MAX_NODE; i++) {
distance[i] = MAX_NODE;
}
scanf("%d%d", &n, &k);
distance[n] = 0;
add(n);
while (bnf(n, k) == 0) {
}
printf("%d\n", distance[k]);
 
return 0;
}
}}}
= 아이디어 =
== 15이원준 ==





1. 오늘의 문제

2. 참가자

3. 코드

3.1. 15이원준

#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<utility>
using namespace std;

int main(){
  int arr[100001] = {0,};
  int N, M, ans;
  queue<pair<int, int>> que;
  cin>> N >> M;
  if(N >= M){
    cout<< N - M << endl;
    return 0;
  }
  que.push(make_pair(N, 0));
  while(que.front().first != M){
    int n, dep;
    n = que.front().first;
    dep = que.front().second;
    que.pop();
    if(n-1 >= 0 && !arr[n-1]){
      arr[n-1] = 1;
      que.push(make_pair(n - 1, dep + 1));
    }
    if(n+1 <= 100000 && !arr[n+1]){
      arr[n+1] = 1;
      que.push(make_pair(n + 1, dep + 1));
    }
    if(n * 2 <= 100000 && !arr[n*2]){
      arr[n*2] = 1;
      que.push(make_pair(n * 2, dep + 1));
    }
  }
  cout<< que.front().second << endl;

}

3.2. 박인서

#include <iostream>
#include <queue>
typedef std::pair<int, int> pair_int;
std::queue<pair_int> q;
bool visit[200001];

int main()
{
	int s, e;
	std::cin >> s >> e;
	if (s < e) {
		q.push(pair_int(s, 0));
		while (q.front().first != e) {
			pair_int tq = q.front();
			if (tq.first < e && !visit[tq.first * 2])
				q.push(pair_int(tq.first * 2, tq.second + 1)), visit[tq.first * 2] = true;
			if (tq.first < e && !visit[tq.first + 1])
				q.push(pair_int(tq.first + 1, tq.second + 1)), visit[tq.first + 1] = true;
			if (tq.first > 0 && !visit[tq.first - 1])
				q.push(pair_int(tq.first - 1, tq.second + 1)), visit[tq.first - 1] = true;
			q.pop();
		}

		std::cout << q.front().second;
	}
	else std::cout << s - e;
	return 0;
}

3.3. 곽정흠

#include <stdio.h>
#define MAX_QUEUE 100000
#define MAX_NODE 100001
 
int distance[MAX_NODE];
int queue[MAX_QUEUE];
int first = 0, last = 0;

void add(int tmp) {
	if (last == MAX_QUEUE) {
		last = 0;
		queue[last++] = tmp;
	}
	else {
		queue[last++] = tmp;
	}
}
int delete(void) {
	if (first == MAX_QUEUE - 1) {
		first = 0;
		return queue[MAX_QUEUE-1];
	}
	else {
		return queue[first++];
	}
}
int bnf(int n, int k) {
	int tmp = delete();
	if (tmp == k) {
		return 1;
	}
	if (tmp * 2 <= k+1) {
		if (distance[tmp * 2] > distance[tmp] + 1) {
			distance[tmp * 2] = distance[tmp] + 1;
			add(tmp * 2);
		}
	}
	if (distance[tmp + 1] > distance[tmp] + 1) {
		distance[tmp +1] = distance[tmp] + 1;
		add(tmp + 1);
	}
	if (tmp - 1 >= 0&&distance[tmp-1]>distance[tmp]+1) {
		distance[tmp -1] = distance[tmp] + 1;
		add(tmp - 1);
	}
	return 0;
}

int main() {
	int n, k;
	for (int i = 0; i < MAX_NODE; i++) {
		distance[i] = MAX_NODE;
	}
	scanf("%d%d", &n, &k);
	distance[n] = 0;
	add(n);
	while (bnf(n, k) == 0) {
		
	}
	printf("%d\n", distance[k]);

	return 0;
}

4. 아이디어

4.1. 15이원준


4.2. 박인서

  • 기본적인 아이디어는 Queue를 이용한 BFS이다.
  • 단 너무 숫자가 커지면 안되므로, 200000이 넘어가면 제한을 한다.
  • 그리고 뒤로 갈 경우 갈 수 있는 방법은 -1밖에 없으므로 그 것을 예외 처리 해준다.

4.3. 곽정흠

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:07
Processing time 0.0424 sec