시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB160951240034.217%

문제

안드로이드 OS에는 휴대폰의 잠금을 풀기 위한 방법 중 패턴을 암호로 사용하는 방법이 있다. 3×3의 9개 점에 번호를 매겨 그중 일부로 하나의 수열을 만들었을 때, 수열에서 인접한 번호의 점을 순서대로 연결해 그려지는 경로를 패턴이라 하자. 이때 패턴의 길이는 패턴을 나타내는 수열의 길이이다.

<그림1> 3×3의 9개 점으로 구성된 잠금화면 예시

패턴에는 다음과 같은 제약이 있다.

  • 패턴의 길이는 3 이상이다.
  • 패턴을 나타내는 수열에는 같은 점이 두번 이상 등장하지 않는다.
  • 수열의 인접한 점을 연결해 만든 선분 위에는 아직 등장하지 않은 점이 있을 수 없다.

<그림2> 패턴의 예시 (예제 1, 2, 3)

예를 들어, 패턴 [1, 2, 3, 6]은 가능한 패턴이지만, [1, 3, 6]은 1-3을 연결하는 선분 위에 아직 등장하지 않은 점이 있으므로 불가능한 패턴이다. [1, 9, 6, 5]는 나중에 5가 등장하지만, 1-9를 그릴 때는 5가 등장하지 않았으므로 불가능한 패턴이며, [1, 5, 9, 6, 5]는 점이 중복해서 등장해 불가능한 패턴, [1, 5, 9, 6, 4]는 가능한 패턴이다.

패턴을 나타내는 수열이 입력되었을 때, 가능한 패턴인지 알고 싶다.

입력

첫 번째 줄에 패턴의 길이 L을 입력받는다.

다음 줄에 L개에 걸쳐 패턴을 나타내는 수열 Ai (1 ≤ iL)를 입력받는다.

출력

유효한 패턴이라면 "YES", 그렇지 않다면 "NO"를 출력한다.

제한

  • 3 ≤ L ≤ 9
  • 1 ≤ Ai​ ≤ 9

예제 입력 1

4
1 2 3 6

예제 출력 1

YES

예제 입력 2

3
1 3 6

예제 출력 2

NO

예제 입력 3

4
1 9 6 5

예제 출력 3

NO

예제 입력 4

5
1 5 9 6 5

예제 출력 4

NO

예제 입력 5

5
1 5 9 6 4

예제 출력 5

YES

출처

University > 경인지역 6개대학 연합 > shake! 2019 A번