https://www.acmicpc.net/problem/3136
이거 푸는데 내가 시도하는 방법이
존나 큰 배열 하나 만들고 거기에 점 찍은거 표시하고 점 다 찍으면 방의 수를 하나하나 세는 무식한 방법임
테스트에서 계속 런타임 에러가 나는데,
근데 배열 크기가 무한하지도 않고 충분히 크지도 않으니
큰 데이터가 들어오면 계속 세그먼트 폴트가 나는것같음
시간도 엄청 오래걸리겠지
제출된 답안보면 무슨 100ms안에 풀던데
원래 이런 알고리즘 문제 풀기 전에
이산수학, 자료구조, 알고리즘 공부 존나게 하고 나서 푸는게 순서냐?
어렵네
4방향 100000 칸갈 수있다면 그걸 배열로 좌표 표현 하면 pow(20만, 2), 좌표당 1바이트 정보만 가져도 37기가!
두 인트 배열 x,y에 처음 0일때 각기 0,0을 넣고 입력된 차려대로의 수에 따라 0,1->1,1.....이런식 입력 시키고 나중에 입력된 좌표가 겹치는 횟수를 계산시키면 그 결과가 방 갯수임 참고로 겹치는 횟수란 0,3이 네개이면 4-1식으로계산
아 맞다 엑스자 식으로 겹치는 점도 추가로 계산 시켜서 더하면됨
내가 보기에 그럼 안될거 같은데... 정점에서 갈라져나온 라인이 도형을 만든다는 보장이 없으니까
아... 평면그래프에서 면의 개수 + 꼭지점의 개수 = 변의 개수 + 1 이란걸 이용하는거구나
이런건 이산수학 그래프이론 모르면 못풀겠네
들어보고 대충 그려 봤는데 도형수 = min( 선분수(교점을 만나기 전 또는 선분의 끝점까지), 교점수) 같은데 맞냐
아 아니구나
비전공자가 말한부분에 지나간 길을 다시 지나가는 경우를 포함시키면될듯
생각해보니 그래프이론 꼭 몰라도되고 직관으로 잘 깨달을수도 잇을듯 꼭지점이 겹칠때마다 면이 하나 생긴다고... 비전공자 존나천재네 시발 난 왜이렇게 멍청한거같냐
쟤는 전공자도 아닌데
이미 지나간점을 지나가면 무조건 한면이 생기겟호호
시발 부럽다 난왤캐멍청하냐
만약 생각한 알고리즘이 아무리 무식한거라도 배열의 크기만 자유자재로 크기에 맞게만 해주면 해결될경우 vector 클래스 쓰면됨 ㅇㅇ 아니면 linked list로 동적할당으로 자료 넣어주던가 근데 linked list도 안배웟다면 뭐.. 걍 vector 써야지
인접한 점들끼리 겹치는 점 횟수도 빼줘야함 예를들어서 1,0->0,0->1,0->0,0->1,0->0,0이면 4-4=0
자살하러갑니다