이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 5 번째 글 입니다.

  • Part 1 - 백준(1003번): 피보나치 함수
  • Part 2 - 백준(1010번): 다리놓기
  • Part 3 - 백준(1012번): 유기농 배추
  • Part 4 - 백준(10159번): 저울
  • Part 5 - This Post
  • Part 6 - 백준(1018번): 체스판 다시 칠하기
  • Part 7 - 백준(1018번): 체스판 다시 칠하기
  • Part 8 - 백준(1022번): 소용돌이 예쁘게 출력하기
  • Part 9 - 백준(10775번): 공항
  • Part 10 - 백준(10816번): 숫자 카드2
  • Part 11 - 백준(10816번): 숫자카드 2
  • Part 12 - 백준(10819번): 차이를 최대로
  • Part 13 - 백준(10830번): 행렬 곱셈
  • Part 14 - 백준(10844번): 쉬운 계단수
  • Part 15 - 백준(10868번): 최소값
  • Part 16 - 백준(1092번): 배
  • Part 17 - 백준(11003번): 최솟값 찾기
  • Part 18 - 백준(1102번): 발전소
  • Part 19 - 백준(11048번): 이동하기
  • Part 20 - 백준(11053번): 가장 긴 증가하는 부분 수열
  • Part 21 - 백준(11054번): 가장 긴 바이토닉 부분 수열
  • Part 22 - 백준(11055번): 가장 긴 증가하는 부분 수열2
  • Part 23 - 백준(11057번): 오르막 수
  • Part 24 - 백준(1120번): 문자열
  • Part 25 - 백준(11403번): 경로 찾기
  • Part 26 - 백준(11404번): 플루이드
  • Part 27 - 백준(1149번): RGB 거리
  • Part 28 - 백준(11559번): puyo puyo
  • Part 29 - 백준(11655번): ROT13
  • Part 30 - 백준(1167번): 트리의 지름
  • Part 31 - 백준(11722번): 가장 감소하는 부분 수열
  • Part 32 - 백준(12015번): 가장 긴 증가하는 부분 수열(LIS) 2
  • Part 33 - 백준(12851번): 숨바꼭질2
  • Part 34 - 백준(12852번): 1로 만들기 2
  • Part 35 - 백준(12865번): 평범한 배낭
  • Part 36 - 백준(1300번): K번째 수
  • Part 37 - 백준(1325번): 효율적인 해킹
  • Part 38 - 백준(13549번): 숨바꼭질3
  • Part 39 - 백준(13913번): 숨바꼭질4
  • Part 40 - 백준(14002번): 가장 긴 증가하는 부분 수열 4
  • Part 41 - 백준(1431번): 시리얼 넘버
  • Part 42 - 백준(1436번): 영화감독 숌
  • Part 43 - 백준(14499번): 주사위 굴리기
  • Part 44 - 백준(14888번): 연산자 끼워넣기
  • Part 45 - 백준(14889번): 스타트와 링크
  • Part 46 - 백준(14891번): 톱니바퀴
  • Part 47 - 백준(15658번): 연산자 끼워넣기 2
  • Part 48 - 백준(15686번): 치킨 배달
  • Part 49 - 백준(1697번): 숨바꼭질
  • Part 50 - 백준(1697번): 숨바꼭질
  • Part 51 - 백준(1707번): 이분 그래프(Bipartite Graph)
  • Part 52 - 백준(1708번): 볼록 껍질
  • Part 53 - 백준(17136번): 색종이 붙이기
  • Part 54 - 백준(1717번): 집합의 표현
  • Part 55 - 백준(17298번): 오큰수
  • Part 56 - 백준(17626번): Four Squares
  • Part 57 - 백준(18870번): 좌표 압축
  • Part 58 - 백준(1890번): 점프
  • Part 59 - 백준(1918번): 후위 표기식
  • Part 60 - 백준(1929번): 소수 구하기
  • Part 61 - 백준(1963번): 소수 경로
  • Part 62 - 백준(1965번): 상자넣기
  • Part 63 - 백준(1976번): 여행가자
  • Part 64 - 백준(1987번): 알파벳
  • Part 65 - 백준(1992번): 쿼드트리
  • Part 66 - 백준(2003번): 수들의 합2
  • Part 67 - 백준(20040번): 사이클 게임
  • Part 68 - 백준(2042번): 구간 합 구하기
  • Part 69 - 백준(2108번): 통계학
  • Part 70 - 백준(2110번): 공유기 설치
  • Part 71 - 백준(2156번): 포도주 시식
  • Part 72 - 백준(2193번): 이친수
  • Part 73 - 백준(2231번): 분해합
  • Part 74 - 백준(2250번): 트리의 높이와 너비
  • Part 75 - 백준(2293번): 동전 1
  • Part 76 - 백준(2294번): 동전 2
  • Part 77 - 백준(2343번): 기타 레슨
  • Part 78 - 백준(2468번): 안전 영역
  • Part 79 - 백준(2512번): 예산
  • Part 80 - 백준(2529번): 부등호
  • Part 81 - 백준(2565번): 전깃줄
  • Part 82 - 백준(2581번): 소수
  • Part 83 - 백준(2583번): 영역구하기
  • Part 84 - 백준(2630번): 색종이 만들기
  • Part 85 - 백준(2644번): 촌수계산
  • Part 86 - 백준(2667번): 단지번호붙이기
  • Part 87 - 백준(2751번): 수 정렬하기 2
  • Part 88 - 백준(2798번): 블랙잭
  • Part 89 - 백준(2904번): 수학은 너무 쉬워
  • Part 90 - 백준(2986번): 파스칼
  • Part 91 - 백준(3015번): 오아시스 재결합
  • Part 92 - 백준(3190번): 뱀
  • Part 93 - 백준(3190번): 벽 부수고 이동하기
  • Part 94 - 백준(4195번): 친구 네트워크
  • Part 95 - 백준(4948번): 베르트랑 공준
  • Part 96 - 백준(4963번): 섬의 개수
  • Part 97 - 백준(4991번): 로봇 청소기
  • Part 98 - 백준(5373번): 큐빙
  • Part 99 - 백준(5437번): 불
  • Part 100 - 백준(6171번): 땅따먹기
  • Part 101 - 백준(6603번): 로또
  • Part 102 - 백준(6603번): 로또
  • Part 103 - 백준(7562번): 나이트의 이동
  • Part 104 - 백준(7568번): 덩치
  • Part 105 - 백준(7576번): 토마토
  • Part 106 - 백준(7579번): 앱
  • Part 107 - 백준(7785번): 회사에 있는 사람
  • Part 108 - 백준(9012번): 괄호
  • Part 109 - 백준(9020번): 골드바흐의 추측
  • Part 110 - 백준(9184번): 신나는 함수 실행
  • Part 111 - 백준(9251번): LCS
  • Part 112 - 백준(9421번): 소수상근수
  • Part 113 - 프로그래머스: 가장 큰 정사각형 찾기
▼ 목록 보기

목차

▼ 내리기

실버1 : DFS 문제이다.

풀이

DFS와 동적계획법이 섞인 문제이다. 일단, 특정 위치까지 갈 수 있는 모든 경우의 수를 구해야 하는데, 그냥 방문할 때마다 count를 늘려준다면, 중복해서 방문하는 곳이 너무 많아 비효율 적이다.

그렇기 때문에, 특정 시작 지점에서 가질 수 있는 경우의 수를 잡고, 이 경우의 수를 잡기 위해서는 다음 방문의 경우의 수를 더해주는 것으로 해결할 수 있다.

이 때, 중간 방문 지점이 0인 경우 그냥 시작에서 끝까지의 답을 구하면되고, 그렇지 않을 경우 중간지점까지, 그리고 중간지점에서 끝지점까지 구하는 것으로 문제를 해결한다.

Code

import string

a = input()

alphabet_lower = string.ascii_lowercase
alphabet_upper = string.ascii_uppercase
ret_string = ""
for char in a:
    if char in alphabet_lower:
        pos = alphabet_lower.find(char)
        char = alphabet_lower[(pos + 13) % len(alphabet_lower)]
    elif char in alphabet_upper:
        pos = alphabet_upper.find(char)
        char = alphabet_upper[(pos + 13) % len(alphabet_upper)]
    ret_string += char

print(ret_string)

Reference