Algorithm/๋ฌธ์ œํ’€์ด

[๋ฐฑ์ค€] 1925๋ฒˆ - ์‚ผ๊ฐํ˜• (C++)

moaoh 2023. 7. 15. 16:28

 

1925๋ฒˆ: ์‚ผ๊ฐํ˜•

ํ‰๋ฉด์ƒ์— ์„ธ ๊ฐœ์˜ ์ ์ด ์ฃผ์–ด์ง€๋ฉด, ๊ทธ ์„ธ ์ ์œผ๋กœ ์ด๋ฃจ์–ด์ง€๋Š” ์‚ผ๊ฐํ˜•์€ ์œ ์ผํ•˜๊ฒŒ ๊ฒฐ์ •๋œ๋‹ค. ๋˜๋Š”, ์‚ผ๊ฐํ˜•์ด ์ด๋ฃจ์–ด์ง€์ง€ ์•Š๊ธฐ๋„ ํ•œ๋‹ค. ์„ธ ์ ์˜ ์ขŒํ‘œ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ ๋‹ค์Œ์— ๋”ฐ๋ผ ์ด ์‚ผ๊ฐํ˜•์˜ ์ข…๋ฅ˜๋ฅผ

www.acmicpc.net

๋ฌธ์ œ

ํ‰๋ฉด์ƒ์— ์„ธ ๊ฐœ์˜ ์ ์ด ์ฃผ์–ด์ง€๋ฉด, ๊ทธ ์„ธ ์ ์œผ๋กœ ์ด๋ฃจ์–ด์ง€๋Š” ์‚ผ๊ฐํ˜•์€ ์œ ์ผํ•˜๊ฒŒ ๊ฒฐ์ •๋œ๋‹ค. ๋˜๋Š”, ์‚ผ๊ฐํ˜•์ด ์ด๋ฃจ์–ด์ง€์ง€ ์•Š๊ธฐ๋„ ํ•œ๋‹ค. ์„ธ ์ ์˜ ์ขŒํ‘œ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ ๋‹ค์Œ์— ๋”ฐ๋ผ ์ด ์‚ผ๊ฐํ˜•์˜ ์ข…๋ฅ˜๋ฅผ ํŒ๋‹จํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

  1. ์„ธ ์ ์ด ์ผ์ง์„  ์œ„์— ์žˆ์œผ๋ฉด - ‘์‚ผ๊ฐํ˜•์ด ์•„๋‹˜’ ์ถœ๋ ฅํ•  ๋•Œ๋Š” X
  2. ์„ธ ๋ณ€์˜ ๊ธธ์ด๊ฐ€ ๊ฐ™์œผ๋ฉด - ‘์ •์‚ผ๊ฐํ˜•’ ์ถœ๋ ฅํ•  ๋•Œ๋Š” JungTriangle
  3. ๋‘ ๋ณ€์˜ ๊ธธ์ด๊ฐ€ ๊ฐ™์œผ๋ฉด
    1. ๊ฐ€์žฅ ํฐ ๊ฐ์ด 90°๋ณด๋‹ค ํฌ๋ฉด - ‘๋‘”๊ฐ์ด๋“ฑ๋ณ€์‚ผ๊ฐํ˜•’ ์ถœ๋ ฅํ•  ๋•Œ๋Š” Dunkak2Triangle
    2. ๊ฐ€์žฅ ํฐ ๊ฐ์ด 90°์ด๋ฉด - ‘์ง๊ฐ์ด๋“ฑ๋ณ€์‚ผ๊ฐํ˜•’ ์ถœ๋ ฅํ•  ๋•Œ๋Š” Jikkak2Triangle
    3. ๊ฐ€์žฅ ํฐ ๊ฐ์ด 90°๋ณด๋‹ค ์ž‘์œผ๋ฉด - ‘์˜ˆ๊ฐ์ด๋“ฑ๋ณ€์‚ผ๊ฐํ˜•’ ์ถœ๋ ฅํ•  ๋•Œ๋Š” Yeahkak2Triangle
  4. ์„ธ ๋ณ€์˜ ๊ธธ์ด๊ฐ€ ๋ชจ๋‘ ๋‹ค๋ฅด๋ฉด
    1. ๊ฐ€์žฅ ํฐ ๊ฐ์ด 90°๋ณด๋‹ค ํฌ๋ฉด - ‘๋‘”๊ฐ์‚ผ๊ฐํ˜•’ ์ถœํ˜ํ•  ๋•Œ๋Š” DunkakTriangle
    2. ๊ฐ€์žฅ ํฐ ๊ฐ์ด 90°์ด๋ฉด - ‘์ง๊ฐ์‚ผ๊ฐํ˜•’ ์ถœ๋ ฅํ•  ๋•Œ๋Š” JikkakTriangle
    3. ๊ฐ€์žฅ ํฐ ๊ฐ์ด 90°๋ณด๋‹ค ์ž‘์œผ๋ฉด - ‘์˜ˆ๊ฐ์‚ผ๊ฐํ˜•’ ์ถœ๋ ฅํ•  ๋•Œ๋Š” YeahkakTriangle

์ž…๋ ฅ

์ฒซ์งธ ์ค„๋ถ€ํ„ฐ ์…‹์งธ ์ค„๊นŒ์ง€ ์‚ผ๊ฐํ˜•์„ ์ด๋ฃจ๋Š” ์ ์˜ x์ขŒํ‘œ์™€ y์ขŒํ‘œ๊ฐ€ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. ์ž…๋ ฅ๋˜๋Š” ์ˆ˜๋Š” ์ ˆ๋Œ“๊ฐ’์ด 10,000์„ ๋„˜์ง€ ์•Š๋Š” ์ •์ˆ˜์ด๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ์„ธ ์ขŒํ‘œ๋Š” ์ค‘๋ณต๋˜์ง€ ์•Š๋Š”๋‹ค.


์ถœ๋ ฅ

์œ„์˜ ๊ฒฝ์šฐ์— ๋”ฐ๋ผ ์‚ผ๊ฐํ˜•์˜ ์ข…๋ฅ˜๊ฐ€ ๋ฌด์—‡์ธ์ง€ ์ถœ๋ ฅํ•œ๋‹ค.


์˜ˆ์ œ ์ž…๋ ฅ 1

0 0
-3 -3
-3 0

์˜ˆ์ œ ์ถœ๋ ฅ 1

Jikkak2Triangle

์˜ˆ์ œ ์ž…๋ ฅ 2

1 1
0 0
2 100

์˜ˆ์ œ ์ถœ๋ ฅ 2

DunkakTriangle

์˜ˆ์ œ ์ž…๋ ฅ 3

10000 10000
2580 2580
-10000 -10000

์˜ˆ์ œ ์ถœ๋ ฅ 3

X

ํ’€์ด๊ณผ์ •

๋ฌธ์ œ ์ž์ฒด๊ฐ€ ์ˆ˜ํ•™์˜ ํ”ผํƒ€๊ณ ๋ผ์Šค ์ •๋ฆฌ๊ฐ€ ๊ธฐ๋ฐ˜์ด ๋˜๋Š” ๋ฌธ์ œ์ด๋‹ค๋ณด๋‹ˆ ๋ฌธ์ œ๋ฅผ ์‹œ์ž‘ํ•˜๊ธฐ์— ์•ž์„œ ๊ธฐ๋ณธ์ ์œผ๋กœ ์ˆ™์ง€๋ฅผ ํ•ด์•ผํ•˜๋Š” ์ˆ˜ํ•™์ ์ธ ์ง€์‹์ด ํ•„์š”ํ•œ ๋ฌธ์ œ์˜€๋‹ค.

๋ฌธ์ œ์—์„œ ์ž…๋ ฅ๊ฐ’์ด 3๊ฐœ์˜ ์ ์˜ x, y๋กœ ์ฃผ์–ด์ง€๊ธฐ๋•Œ๋ฌธ์— ์ ๊ณผ ์ ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ๊ณต์‹์„ ์•Œ๊ณ ์žˆ์–ด์•ผํ–ˆ๊ณ 

์ •์‚ผ๊ฐํ˜•, ์‚ผ๊ฐํ˜•(๋ถˆ๊ฐ€), ์˜ˆ๊ฐ์‚ผ๊ฐํ˜•, ์ง๊ฐ์‚ผ๊ฐํ˜•, ๋‘”๊ฐ์‚ผ๊ฐํ˜• ์ด 5๊ฐ€์ง€์˜ ์กฐ๊ฑด๋“ค์„ ํŒ๋ณ„ํ• ์ค„ ์•Œ์•„์•ผํ–ˆ์—ˆ๋‹ค.

  • ์ •์‚ผ๊ฐํ˜• ์ ๊ณผ ์ ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ ๊ณต์‹์œผ๋กœ ๊ตฌํ•œ a, b, c์˜ ๊ธธ์ด๊ฐ€ ๋ชจ๋‘ ๊ฐ™์œผ๋ฉด ์ •์‚ผ๊ฐํ˜•์œผ๋กœ ํŒ๋ณ„ํ•  ์ˆ˜ ์žˆ๋‹ค.
  • ์‚ผ๊ฐํ˜•(๋ถˆ๊ฐ€) ๊ฐ€์žฅ ๊ธด c์˜ ๊ธธ์ด๊ฐ€ a + b ๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์œผ๋ฉด ์‚ผ๊ฐํ˜•์˜ ์„ฑ๋ฆฝ์ด ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค (c ≥ a + b)
  • ์˜ˆ๊ฐ์‚ผ๊ฐํ˜• c^2 ๋ณด๋‹ค a^2 + b^2 ์ด ๋” ํฌ๋‹ค๋ฉด ์˜ˆ๊ฐ์‚ผ๊ฐํ˜•์ด๋‹ค. (c^2 < a^2 + b^2)
  • ์ง๊ฐ์‚ผ๊ฐํ˜• c^2 ๋ณด๋‹ค a^2 + b^2 ์ด ๊ฐ™๋‹ค๋ฉด ์ง๊ฐ์‚ผ๊ฐํ˜•์ด๋‹ค. (c^2 = a^2 + b^2)
  • ๋‘”๊ฐ์‚ผ๊ฐํ˜• c^2 ๋ณด๋‹ค a^2 + b^2 ์ด ๋” ์ž‘๋‹ค๋ฉด ๋‘”๊ฐ์‚ผ๊ฐํ˜•์ด๋‹ค. (c^2 > a^2 + b^2)

์œ„์™€ ๊ฐ™์€ ์กฐ๊ฑด๋“ค์„ ์ˆ™์ง€ํ•˜๊ณ  ์ฝ”๋“œ์— ๋Œ€์ž…ํ•˜๋ฉด ๋˜๋Š” ํ˜•์‹์˜ ๋ฌธ์ œ์˜€๋‹ค.

code

#include <iostream>
#include <stdlib.h>
#include <math.h>

struct Point
{
	int	x;
	int	y;
};

int		triangle(double c, double a, double b) 
{
	if (std::sqrt(c) >= (std::sqrt(a) + std::sqrt(b))) {
		std::cout << "X";
		return (1);
	}
	if (c > (a + b)) std::cout << "Dunkak";
	if (c == (a + b)) std::cout << "Jikkak";
	if (c < (a + b)) std::cout << "Yeahkak";
	return (0);
}

int		main(void)
{
	struct Point p1, p2, p3;
	double	a, b, c;
	int		n = 0;

	std::cin >> p1.x >> p1.y;
	std::cin >> p2.x >> p2.y;
	std::cin >> p3.x >> p3.y;
	a = pow(p2.x - p1.x, 2) + pow(p2.y - p1.y, 2);
	b = pow(p3.x - p2.x, 2) + pow(p3.y - p2.y, 2);
	c = pow(p3.x - p1.x, 2) + pow(p3.y - p1.y, 2);
	if (a >= b && a >= c) n = triangle(a, b, c);
	else if (b >= a && b >= c) n = triangle(b, c, a);
	else if (c >= a && c >= b) n = triangle(c, b, a);
	if (!n)
		if (a == b || b == c || c == a) std::cout << "2";
	if (!n && a == b && b == c && c == a) std::cout << "Jung";
	if (!n) std::cout << "Triangle";

	return(0);
}


ํ›„๊ธฐ

์ตœ๋Œ€ํ•œ ์ฝ”๋“œ๋ฅผ ๊น”๋”ํ•˜๊ฒŒ ์งค๋ ค๊ณ ํ•˜๋‹ค๋ณด๋‹ˆ ์˜คํžˆ๋ ค ๋ฐ˜๋ก€๋“ค์ด ๋งŽ์ด ๋‚˜์™€์„œ ๋””๋ฒ„๊น…์ด ๋” ํž˜๋“ค์—ˆ๋˜ ๊ฑฐ ๊ฐ™๋‹ค.

์กฐ๊ธˆ ๋” ์ฒ ์ €ํžˆ ๊ตฌ์ƒํ•ด์„œ ๋ฌธ์ œ์˜ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๋„๋ก ํ•ด์•ผํ•  ๊ฑฐ ๊ฐ™๋‹ค.