W2 — 통합 해설집 (GUIDE): 2503 단백질폴딩 (Protein)

3D 단백질 접기(folding) 최적화. ANATOMY + ATTACK + DEBUG_KIT 통합 + 개선 전략 + 참고문헌.

목차

1. 한눈에 보기
2. 폴딩 기하학 완전 해부
3. 공략 우선순위와 베이스라인
4. SA 적용 가이드
5. 함정과 즉사 회피
6. 참고문헌 및 유사문제

1. 한눈에 보기

점수 공식

SCORE = Σ_{(z,y,x)} Σ_{6방향} weight(sym[z,y,x]) × weight(sym[인접])
제약: 모든 원소 ∈ [0,100)³, 겹침 0건

• S×S=900, S×N=300, N×N=100, H×H=1.
• 무거운 원소(S/N/O) 인접 밀집이 고득점의 핵심.

2. 폴딩 기하학 완전 해부

fold_amino(aminoNum, front, axis, anticlockwise)

• baseElem = aminoNum의 connector 원소 (관절).
• front=true: aminoNum 앞쪽(0~aminoNum-1) 아미노산들 전체 회전.
• front=false: aminoNum 뒤쪽(aminoNum+1~끝) 회전.
• axis: 0=X, 1=Y, 2=Z축. anticlockwise: 회전 방향.
• 90° 강체 회전 (좌표는 정수 유지).
• 대규모 구조 변화 (여러 아미노산 동시 이동).

fold_element(aminoNum, elementNum, front, axis, anticlockwise)

• baseElem = gElements[aminoNum][elementNum].
• 제약: front/back 구간에 connector 원소가 있으면 no-op(return).
• 즉 elementNum과 connector 사이 구간만 회전 가능.
• connector를 넘어 회전 불가 → 꼬리 부분만 미세 조정.

누적성

• fold는 절대 누적 (현재 구조에서 추가 회전).
• 되돌리려면 정확히 역방향 fold (같은 base, 반대 axis/방향).
• 복구가 까다로우므로 백업 후 fold → 위반 시 백업 복원이 안전.

connector의 역할

• 각 아미노산의 고정 관절점 (gAminoType[ ].connectorIdx).
• 아미노산 사슬이 connector를 힌지로 접힘.
• 원소 단위 회전은 connector를 넘지 못함 → 아미노산 내부 세부 조정만.

3. 공략 우선순위와 베이스라인

1차: 합법 100% 보장 (0점 회피)

• 초기 일자 상태는 합법 → 아무 fold 안 하면 최소 점수 보장.
• fold 적용 후 반드시 protein()으로 읽어 [0,100)³ + 겹침 점검.
• 위반 시 마지막 합법 상태로 복원.

2차: 무거운 원소 클러스터링

• fold_amino로 아미노산들을 중앙으로 접어 구형/직육면체 형성.
• S/N 원소가 인접하도록 아미노산 방향 조정.
• S를 포함한 아미노산(type 4: HSCHHCHNHHCOOH, type 12: CHHHSCHHCHHCHNHHCOOH)을 중심에 배치.

베이스라인 코드 흐름

void process() {
    int aminoCount = protein(backup);   // 초기 구조 읽기
    long long best = score(backup);
    // SA 또는 그리디 폴딩
    for (시도) {
        fold_amino(무작위 amino, front, axis, dir);  // 또는 fold_element
        protein(current);  // 갱신된 구조 읽기
        if (verify(current) && score(current) > best) {
            best = score(current); backup = current;
        } else {
            역방향 fold로 복구; (또는 backup 복원)
        }
    }
}

4. SA 적용 가이드

매개변수 (추정 시작점)

• INITIAL_TEMP=1000, FINAL_TEMP=0.01, COOLING_RATE=0.9995, ITERS_PER_TEMP=40.
• TC당 0.2~0.3초 (10TC).

이웃 생성

• 무작위 fold_amino (aminoNum, front, axis, anticlockwise).
• 무작위 fold_element (미세 조정, 단 connector 제약).

수용/복구

• 점수 증가 → 즉시 수용.
• 감소 → exp(Δ/temp) 확률로 수용.
• verify 위반 → 무조건 복구.

5. 함정과 즉사 회피

치명 함정

1. verify 실패 = 0점 (PENALTY 1e11이 아닌 0). 게다가 break로 이후 TC 스킵.
2. 범위 위반: 폴딩 시 회전 반경이 크면 쉽게 100 초과/음수. 중앙(50) 여유 ±50.
3. 겹침: 여러 fold 후 원소가 같은 격자점에 → verify 실패.
4. compactProtein 버그: user.cpp의 compactProtein은 user 로컬 백업만 이동, 실제 gElements는 안 움직임 → 실전에서는 fold로만 조작.
5. fold 역연산 주의: 정확히 같은 base, 반대 axis/방향이어야 복구. 누적 오류 위험.

안전 전략

• 보수적 fold (작은 회전부터).
• 매 fold 후 protein() 읽기 + 점검.
• 위반 시 즉시 백업 복원 (fold 역연산 대신 백업 상태에서 재시작이 안전 — 단, gElements는 채점기가 관리하므로 실제로는 protein()으로 읽은 후 fold API로만 되돌림 가능).
• 최악 회피: 그냥 초기 일자 상태 유지해도 0점은 아님. 보수적으로 시작.

6. 참고문헌 및 유사문제

학술

• Protein Folding Problem (HP model): 격자 상 단백질 접기. 본 문제와 유사.
• Lattice protein folding: HP(Hydrophobic-Polar) 모델. SA/MC 기반 접기.
• 3D puzzle/cube folding: 3D 기하학 회전 최적화.

삼성/대회 유사

• 삼성 Professional 난이도 folding류: 구조 최적화 변형.
• ICPC/IOI 기하 + SA: 회전 기반 탐색.

알고리즘

• Simulated Annealing: 폴딩 탐색 표준.
• Monte Carlo: 단백질 접기 고전 기법.
• Genetic Algorithm: 구조 진화.

디버그

• DEBUG_KIT.md + debug_snippet.cpp (verify, SCORE 분해, heavy 인접도).