(BOJ) 1339 단어수학

문제:https://www.acmicpc.net/problem/1339

문제 풀이1: 백트래킹 이용

void func(int cur,int pos, int cur_sum,int sum,int visit)

cur: 몇번째 단어를 보는 중인지 알려줌

pos: 현재 보는 단어에서의 위치

cur_sum: 현재 보는 단어에서 현재위치까지의 합

sum: 지금까지의 합

visit: 지금껏 사용한 숫자를 표시

모든 수를 대입해보고 가장 결과 값이 큰 값을 출력

소스 코드: https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-1339

결과:

메모리: 1992KB

시간: 632ms

문제 풀이2: 

각각의 위치에 따른 값을 부여

ex) ABC

C위치의 값은 1

B위치의 값은 10

A위치의 값은 100

v['C'-'A']+=1;

v['B'-'A']+=10;

v['A'-'A']+=100; 으로 단어마다 각각 구해서 더해줌

sort한 다음

가장 큰 값을 가지는 것부터 차례대로 9부터 값을 매김 (9,8,7,...)

ex)

arr['A'-'A']=9;

arr['B'-'A']=8;

arr['C'-'A']=7;

마지막으로 단어들에 arr값 대입하여 값 더한 후 결과 출력

소스 코드:https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-1339

결과:

메모리: 1992KB

시간: 0ms