[문제스포주의]
https://www.acmicpc.net/problem/1591
문제 분류는 오일러라고 함
입력에 등장한 숫자들을 각각 정점이라고 생각하고 정점마다 차수를 구하면
M은 3이고
정답수열 :
12345
예제입력:
123
234
345
일때
adj [here][there] = 1
해주는 방식으로 그래프를 기록한 다음 종만북 오일러 순회 dfs 돌리면 되는데
근데 문제는, 수열에 중복되는 값이 존재할때임.
종만북에서는 dfs 가 한번 순회할때마다 adj [here][there] 을 1씩 빼주는데
이 방법은 정답수열이 12312345 같이 중복되는 값이 존재할 경우에 문제가생김.
1 ㅡ 2 ㅡ 3 까지 간다음 다시 1에서 출발하려는데 가려는데 1에는 남아있는 간선이없어서 에러가 나네
그렇다고 처음에 그래프를 기록할때
adj [here][there] += 1
방식 으로 기록하면
정답수열: [1, 2, 3, 4, 5]
차수 : [1, 2, 3 , 2, 1]
가 되서 홀수 차수가 2개 이상이라 오일러로 못풀고. 애초에 M이 2로 고정되서 숫자 두개씩만 준다면 이 방법으로 풀수 있겠지만 M이 막 변화한다는거에서 막히네
그래서 저거 문제 조건중에
"같은 값의 수열은 반복되지 않는다" (첫번째 그래프 기록방식으로 풀경우)
또는
"M 은 2로 고정" (두번째 기록 방식)
추가 되야하는거 아님? 그렇지 않더라도 풀수 있는데 내가 내공이 딸리는건가 ㅠㅠ
긴글 ㅈㅅ하다
입력이 123 234 345 이런 식으로 들어오면 정점을 12, 23, 34, 45 이렇게 4개로 보고 12-23, 23-34, 34-45 이렇게 간선이 연결되어 있다고 생각하면 됨
해봤는데 M=3 에서는 되는데.. 예를 들어 M=5 이고 12345674321767 이 있다고 하면 똑같이 해도 안풀림.. 케이스를 하나 들어줬는데도 바로 이해가 안되는거 보면 뭔가 기본 베이스적인 면에서 내가 놓치고 있는게 있는거같은데..
설마 12-23 으로 본건 아니지? 당연히 12345 들어오면 1234 -2345로 봤겠지?
애초에 12, 23 ,34 ,45 로 나눠서 본다는 발상 자체를 어떻게 하는거임? 걍 ps 오래하다보면 대충 정형화되서 이것저것 해볼게 생각나는건가 알수있는건가 아니면 이 문제를 꿰뚫고 있는 어떤 베이스가 존재 하는건가
잘 생각해보면 안 될 수가 없는 방법임
아 ㅇㅋ 잠만 다시해봄
아 이제 머릿속에서 이미지화 됬다. 근데 갤주 이 문제 예전에 풀어봤었음? 어케 바로나옴? 글쓰고 뭐 이상한 표현있나 다시읽어보는데 갑자기 답글 개빨리 달림 ㄷㄷ
풀어보긴 했는데 주어진 입력을 그래프로] 변환시키려고 해보면 저방법 말고 딱히 생각나는거 없을껄