백준 알고리즘 4084, Viva la Diferencia 문제 풀이 코드 공개

백준 알고리즘 4084, Viva la Diferencia 문제 풀이 코드 공개 

 

문제

네 개의 양의 정수 a, b, c, d가 있을 때, 아래와 같이 차이를 계산할 수 있다.

|a-b| |b-c| |c-d| |d-a|

이렇게 나온 네 개의 수를 이용해서 다시 또 차이를 계산할 수 있다. 이 작업을 모든 네 개의 정수가 같아질 때까지 반복한다.

예를 들어, 1, 3, 5, 9로 시작했을 때를 생각해보자.

1 3 5 9

2 2 4 8 (1)

0 2 4 6 (2)

2 2 2 6 (3)

0 0 4 4 (4)

0 4 0 4 (5)

4 4 4 4 (6)

위의 경우에서 수열은 6번 만에 수렴한다. a, b, c, d가 주어졌을 때, 이 수열이 얼마나 빨리 수렴하는지 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, a, b, c, d가 순서대로 주어진다. 입력의 마지막 줄에는 0이 4개 주어진다. (1 ≤ a,b,c,d ≤ 2,000,000,000)

출력

각 테스트 케이스에 대해서, 수열이 몇 번 만에 수렴하는지 출력한다.

힌트

만약 네 정수가 2n보다 작다면, 3*n번 이내에 수렴한다.

출처

ICPC > Regionals > North America > Southeast USA Regional > 2011 Southeast USA Regional Programming Contest D번

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: kgj291

알고리즘 분류

• 수학
• 구현
• 사칙연산
• 시뮬레이션

#include<stdio.h>

int main(){
	int a,b,c,d;
	while(scanf("%d %d %d %d",&a,&b,&c,&d)){
		if(a == b && c == d && a == c && a == 0)
			break;
		int cnt = 0;
		while(1){
			if(a == b && b == c && c == d)
				break;
			int t = a;
			a -= b;
			b -= c;
			c -= d;
			d -= t;
			if(a<0) a = -a;
			if(b<0) b = -b;
			if(c<0) c = -c;
			if(d<0) d = -d;
			cnt++;
			
		}
		printf("%d\n",cnt);
	}
}

 

5년전에 풀었던 것을 지금 보니.. 참 어렵게도 푼 것 같다