[C++] 백준 1339번 풀이 (단어 수학)

정민경·2023년 1월 16일
0

baekjoon

목록 보기
17/57
post-thumbnail

- 문제 (1339번) : 단어 수학

  • 알파벳 대문자를 입력받았을 때 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔 그 수들을 합할 때 제일 큰 값으로 만드는 문제

- 입력 및 출력

[입력]

  • 첫째 줄에 단어의 개수 N 입력
  • 둘째줄부터 N개의 줄에 단어를 한줄에 하나씩 입력

각 입력값들의 제한범위

  • 단어의 개수 (N) : 1 ≤ N ≤ 10
  • 단어 당 알파벳 개수 (M) : 1 ≤ M ≤ 10
  • 수의 최대 길이 : 8

[출력]

  • 주어진 단어의 합의 최댓값 출력

- 문제 풀이

  1. 입력받은 단어를 하나의 수로 생각해 해결한다.

    • ex) ABC 이면 100A + 10B + 1C 로 생각
  2. 여러개의 단어를 입력받은 경우 위와 같은 방법으로 생각한다.

    • ex) ABC, ABCD 입력받은 경우
      ABC -> 100A + 10B + 1C
      ABCD -> 1000A + 100B + 10C + 1D
      ∴ 1100A + 110B + 11C + 1D 로 생각하면 됨.
  3. 위와같이 계산해 도출해낸 방정식의 계수들을 기준으로 큰 수 -> 작은 수로 내림차순 정렬을 한다.

    • ex) ABC 인 경우 -> 100A + 10B + 1C
      alpha[A] = 100
      alpha[B] = 10
      alpha[C] = 1
      • 이 때 배열 index의 A, B, C는 'A'의 아스키코드값을 뺀 index 값임.
      • ex) alpha[A] == alpha[ A - 'A' ] == alpha[0]
        ex) alpha[B] == alpha[ B - 'A' ] == alpha[1]
        ex) alpha[C] == alpha[ C - 'A' ] == alpha[2]
  4. 3.의 과정에서 정렬한 값을 바탕으로 계수가 가장 큰 문자부터 순서대로 9, 8, 7 ... 1까지 곱해 더해주면 가장 큰 합이 될 수 있다.

    • ex) 3.에서 내림차순으로 정렬했을 때 (100A + 10B + 1C )
      alpha[0] = 100 x 9
      alpha[1] = 10 x 8
      alpha[2] = 1 x 7
      ∴ 900 + 80 + 7 = 987

- 최종 코드


- 참고 링크

0개의 댓글