2469

알고리즘/acmicpc 2015. 2. 14. 13:48 Posted by 아는 개발자

사다리 문제는 간단하다

가로획이 있으면 둘의 위치가 바뀌는 성질만 이용하면 된다.

????가 나타나기 전까지는 ABCD에서 쭉 내려오고

그 이후로는 목표로 한 문자열을 가지고 아래에서 위로 올라간 후

서로 비교하면 된다.

현재 문자열과 목표 문자열의 위치 차이가 2 이상으로 나면 사다리로 만들 수 없으므로

xxxx를 출력하면된다.


문제만 생각하지 말고 사다리의 원리에 대해서 생각해보자

내가 어떻게 가로획을 긋더라도 사다리는 항상 일대일 대응을 이루는데

방금 위에서 설명한 사다리 가로획의 원리를 생각하면 이해하기 쉽다.

두 세로획의 자리를 바꾸는 것이기 때문에 내가 어떻게 자리를 바꾸더라도

1:1대응의 성질은 유지될 수 밖에 없다.

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14
2467  (0) 2015.02.14

2467

알고리즘/acmicpc 2015. 2. 14. 12:42 Posted by 아는 개발자

처음에는 binary search로 접근해서 푸려고했는데

런타임에러가 자꾸 난다... 이유는 모르겠다


그래서 음수 양수를 하나의 배열에 넣고 절대값으로 정렬한 다음

붙어있는 거끼리 음수 양수를 복원한 값으로 더해서

그 중 최소의 값을 구하는 방식으로 문제를 해결했다.


런타임 에러 찾느라 시간이 너무 오래걸렸다... 찾지도 못했으면서 ㅠ

728x90

'알고리즘 > acmicpc' 카테고리의 다른 글

9251  (0) 2015.02.17
2599  (0) 2015.02.15
2436  (0) 2015.02.15
2533  (0) 2015.02.14
2469  (0) 2015.02.14
2467  (0) 2015.02.14