34122번 - 단백질 접기 점수언어 제한

문제

2024년 노벨 화학상은 단백질의 구조를 분석, 설계 및 예측할 수 있는 인공지능 모델을 개발한 연구자에게 수여되었다.

단순한 모형을 가정하고 단백질 접힘 문제를 풀어보자.

이 문제에서 사용할 단백질을 다음과 같은 단순한 모형으로 모델링하자.

• 구성: 단백질은 다수의 아미노산 구슬이 끈으로 순서대로 연결된, 가지가 없는 하나의 사슬이다.
• 배치: 각 구슬은 2차원 정사각형 그리드 위의 점에 위치할 수 있다.
• 연결: 각 구슬을 잇는 끈의 길이는 그리드 간격과 동일하다. 끈으로 연결된 두 구슬은 상하좌우로 인접해야 한다.
• 아미노산 종류: 아미노산 구슬의 종류는 A, B, C 3가지다.
• 각 아미노산 구슬은 겹치지 않아야 한다.

예를 들어, 5개의 아미노산 구슬로 구성된 단백질1, 2와 10개의 아미노산 구슬로 구성된 단백질3은 각각 다음과 같은 모양을 가질 수 있다.

서로 인접한 두 아미노산 구슬 쌍은 연결 상태와 구슬의 종류에 따라 서로 다른 에너지를 가진다. 각 구슬 쌍의 에너지는 다음과 같이 가정한다.

• 연결된 상태: 에너지 값은 구슬의 종류와 연결 방식에 따라 결정된다.

• 에너지 합산: 전체 단백질의 에너지는 모든 인접 구슬 쌍의 에너지 합으로 계산된다.

위에서 예시로 나온 단백질들은 각각 다음과 같이 전체 에너지가 각각 +1, +5, +2로 계산된다.

아미노산 구슬 111개가 연결된 단백질을 2차원 정사각형 그리드에 배치하고, 각 구슬의 종류를 결정하여 모든 인접한 구슬 쌍의 에너지 합이 최소가 되도록 해야 한다. 점수는 모든 인접한 구슬 쌍의 에너지 합 $E$에 대해 $\max(-E, 0)$으로 계산된다. 즉, 에너지 합이 낮을 수록 점수가 높아진다.

정답 제출을 위해 총 221개의 문자를 제출해야 한다.

1. 아미노산 종류 (첫 111개 문자)
   • 각 문자는 A, B, C 중 하나로 아미노산 구슬의 종류를 결정한다.
   • 예: ABCABCABC...
2. 구슬 배치 방향 (마지막 110개 문자)
   • 각 문자는 U, D, R, L 중 하나로 다음 구슬의 방향을 나타낸다.
   • 예: URDDDLLL...

다음은 아미노산 구슬이 10개인 단백질일 때, 이 단백질을 나타내는 답안이다. 실제로는 111개의 아미노산 구슬에 대한 답안을 제출해야함에 주의하자.

입력

출력

제한

힌트