백준 2477번 문제 바로가기 문제에 대한 첫 인상 처음엔 도대체 어떻게 풀어야하지 고민하다가, 하룻밤 자고 나서야(ㅋㅋ) 해결책을 생각해냈다. 방향을 일일히 고려하는것은 어렵기 때문에 일반화해서 풀어내기로 했다. 가장 긴 두 변이 0, 1번째 인덱스가 되도록 하는 숫자를 찾는 것을 목표로 했다. “동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4로 나타낸다.“라고 했기 때문에, ㄱ자 형태의 경우 423131방향의 이동을 찾아내면 되고, 다른 형태의 경우도 314242 142323 231414 처럼 패턴을 구하면 된다. 그 인덱스를 기준으로 $ l(j)*l(j+1) - l(j+3)*l(j+4) $ 를 구하면 원하는 식을 얻어낼 수 있다. ...
백준 11758번 문제 바로가기 세 점이 순서대로 주어지고 CCW(Counter-ClockWise; 반시계방향)인지 CW(ClockWise; 시계방향)인지 알아내느 문제. 보자마자 두 개의 벡터로 표현하면 편하겠다고 생각했다. 예전에 비슷한 문제를 풀어본 기억이 있기에 바로 외적을 떠올렸다. (기울기로 풀다가 엄청 고생했던 기억이…허허) 내 풀이 처음으로 struct 기능을 사용해보았다. 좌표(coordinate; cdn)에 x,y 좌표가 있으므로 struct cdn { int x,y; }; 처럼 작성하면 dot operator(.)로 접근할 수 있다. 함수 안에서는 int나 char 변수를 선언하듯이 cdn을 선언하고 사용하면 된다. 좌표나 특정 의미가 있는 값이 들어올 때 struct을 이용하면 코드가 간결해진다. ...
백준 1064번 문제 바로가기 내 풀이 삼각형의 각 변의 길이를 구하고, 이를 통해서 만들어낸 평행사변형의 둘레의 (최댓값-최솟값)을 구하는 문제. 예제를 이상없이 모두 통과했지만, 실제로 제출해보니 틀렸습니다 에러가 발생해서 많이 당황했다. 크게 바꾼 부분은 다음 두가지다. 세 점이 한 직선상에 있는지 파악하기 세 점이 한 직선상에 있다면 평행사변형을 만들지 못하므로 -1을 출력해야 한다. 제2코사인 법칙을 이용해도 되고, CCW을 이용해서 풀어도 된다. 계산의 정확도 소숫점 자릿수를 고려해줘야하는 문제였다. 오차 범위가 $ < 10^{-9} $ 이므로 double을 사용하고 cout으로 출력하기 전에 cout.precision(20)와 같이 정확도를 우선 지정해주어야 한다. 자꾸만 틀렸던 이유가 바로 여기에 있었다… #include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int main() { double a1, a2, b1, b2, c1, c2; cin >> a1 >> a2 >> b1 >> b2 >> c1 >> c2; double x, y, z; x = sqrt(pow(b2-a2, 2) + pow(b1-a1, 2)); y = sqrt(pow(c2-b2, 2) + pow(c1-b1, 2)); z = sqrt(pow(a2-c2, 2) + pow(a1-c1, 2)); vector<double> vec = {2*(x+y), 2*(y+z), 2*(z+x)}; // using CCW if three dots are on a single line if ((b1-a1)*(c2-a2) == (c1-a1)*(b2-a2)){ cout << -1; return 0; } double ans; ans = *max_element(vec.begin(), vec.end()) - *min_element(vec.begin(), vec.end()); cout.precision(20); cout << ans; return 0; }
백준 2527번 문제 바로가기 나의 풀이 두개의 직사각형의 두 꼭짓점의 좌표가 주어지고, 이를 통해 두 직사각형의 위치관계를 파악하는 문제였다. 처음에는 주어진 x1, y1, p1, q1, x2, y2, p2, q2 좌표를 그대로 사용했다가 12% 정도 채점 하다가 틀렸습니다 에러가 발생했다. 생각해보니 예제처럼 앞의 직사각형의 항상 원점에 가까운 것은 아닌 경우도 있다는 것을 생각하게 되었다. (예제에 이런 케이스를 더 추가해주면 좋겠지만 아쉽다..) 그래서 직사각형별로 tuple로 묶어서 먼저 정렬해준 뒤에 좌표 간 관계를 분석해보았다. ...
백준 14215번 바로가기 나의 풀이 # 입력 import sys bars = list(map(int, sys.stdin.readline().split())) bars = sorted(bars) # 처리 c = bars[-1] d = sum(bars[:2]) if c <= d - 1: print(sum(bars)) else: print(2*d-1) CODE REVIEW 간만에 머리도 식힐 겸 기하학 문제를 풀었다. 삼각형의 결정 조건을 안다면 쉽게 풀어낼 수 있는 문제였다. 수학적으로 표현하자면… let) a<=b<=c, c<a+b, if) c<a+b, ans=a+b+c, else) ans=2*(a+b)-1