120923. 연속된 수의 합

프로그래머스 120923. 연속된 수의 합

 

문제: 연속된 num개의 정수의 합이 total이 되도록 하는 수들을 찾아 배열로 반환

예시 1) num = 3, total = 12
출력: [3, 4, 5]  → 3 + 4 + 5 = 12

예시 2) num = 5, total = 15  
출력: [1, 2, 3, 4, 5]  → 1 + 2 + 3 + 4 + 5 = 15

 

 

해결 방식 

 

1. while 문을 이용한 무차별 대입 (바보 같았다..)

⚠️ 문제점

1. 무한루프 위험
2. 비효율성
3. 복잡함

public int[] solution(int num, int total) {
    int start = total / num;  // 대략적인 시작점
    
    while (true) {
        int sum = 0;
        for (int i = 0; i < num; i++) {
            sum += start + i;  // 연속된 수들의 합
        }
        
        if (sum == total) {
            // 정답 찾음!
            int[] answer = new int[num];
            for (int i = 0; i < num; i++) {
                answer[i] = start + i;
            }
            return answer;
        }
        
        // 합이 작으면 시작점을 높이고, 크면 낮춤
        if (sum < total) {
            start++;
        } else {
            start--;
        }
    }
}

 

 

2. 브루트 포스(완전 탐색)

 

Brute Force : 완전 탐색

: 가능한 모든 경우를 다 시도해보는 방법 

 

특징 

- 답이 있으면 반드시 찾아냄

- 복잡한 로직이 필요 없음

- 모든 경우를 다 확인하므로 비효율적

- 범위를 설정해야함 

public int[] solution(int num, int total) {
    // 범위 설정 (경험적 추정)
    int minStart = total / num - num;
    int maxStart = total / num + num;
    
    // 설정한 범위에서 모든 시작점 시도
    for (int start = minStart; start <= maxStart; start++) {
        int sum = 0;
        
        // 현재 시작점에서 연속된 num개 수의 합 계산
        for (int i = 0; i < num; i++) {
            sum += start + i;
        }
        
        // 합이 target과 같으면 정답!
        if (sum == total) {
            int[] answer = new int[num];
            for (int i = 0; i < num; i++) {
                answer[i] = start + i;
            }
            return answer;
        }
    }
    
    return new int[]{}; // 해가 없는 경우
}

 

 

 

3. 등차수열

 

등차수열 

: 연속된 두 항의 차이가 항상 같은 수열

예시 1: 1, 2, 3, 4, 5     (차이: 1)
예시 2: 3, 5, 7, 9, 11    (차이: 2)  
예시 3: 10, 8, 6, 4, 2    (차이: -2)

 

등차수열의 구성 요소

• 첫째항: 수열의 첫 번째 수
• 공차: 연속된 항들의 차이
• 일반항: n번째 항의 공식

 

등차수열의 일반항 공식

첫째항을 a, 공차를 d라고 하면:
n번째 항 = a + (n-1) × d

 

 

등차수열을 이용하는 경우 

• 데이터 분석 : 연속된 기간의 평균을 구할 때 (월별 매출 추이 분석)
• 게임 개발 : 레벨업 시스템의 경험치 계산 (1레벨 100XP, 2레벨 200XP, ...)
• 금융 : 적금의 월별 납입액 계산 (매월 일정 금액씩 증가하는 적금)
• 알고리즘 최적화 : O(n²) → O(n)으로 개선 (반복문 중첩 → 수식 한 번 계산)

 

등차수열을 문제에 적용하여 해결한다면 공차가 1인 등차수열로 계산 

연속된 num개 수: a, a+1, a+2, ..., a+(num-1)

합 = a + (a+1) + (a+2) + ... + (a+num-1)
   = num×a + (0+1+2+...+(num-1))
   = num×a + num×(num-1)/2

따라서: total = num×a + num×(num-1)/2
정리하면: a = (total - num×(num-1)/2) / num

 

 

최종 코드 🎉

public int[] solution(int num, int total) {
    // 등차수열 합 공식: 0+1+2+...+(num-1) = num×(num-1)/2
    int arithmeticSum = num * (num - 1) / 2;
    
    // 정수 해가 존재하는지 확인
    if ((total - arithmeticSum) % num != 0) {
        return new int[]{}; // 해가 없는 경우
    }
    
    // 시작값(첫째항) 계산
    int start = (total - arithmeticSum) / num;
    
    // 연속된 수들로 배열 생성
    int[] answer = new int[num];
    for (int i = 0; i < num; i++) {
        answer[i] = start + i;
    }
    
    return answer;
}

 

---

 

레벨업 필요 경험치가 일정하게 증가하는 시스템의 예시 코드를 기반으로 등차수열이 실무에서 언제, 어떻게 코드에 녹아져서 사용되는지 한번 더 알아보기!

 

📈 상황 1: 레벨업 필요 경험치가 일정하게 증가하는 시스템

 

게임 기획:

• 1레벨 → 2레벨: 100XP 필요
• 2레벨 → 3레벨: 200XP 필요
• 3레벨 → 4레벨: 300XP 필요
• 매 레벨마다 100XP씩 증가

 

 

public class LevelSystem {
    // 특정 레벨 달성에 필요한 총 경험치 계산
    public int getTotalExpForLevel(int targetLevel) {
        if (targetLevel <= 1) return 0;
        
        // 등차수열의 합: 100 + 200 + 300 + ... + (targetLevel-1)*100
        // = 100 × (1 + 2 + 3 + ... + (targetLevel-1))
        // = 100 × (targetLevel-1) × targetLevel / 2
        
        return 100 * (targetLevel - 1) * targetLevel / 2;
    }
    
    // 현재 경험치로 달성 가능한 레벨 계산
    public int getCurrentLevel(int currentExp) {
        int level = 1;
        
        while (getTotalExpForLevel(level + 1) <= currentExp) {
            level++;
        }
        
        return level;
    }
    
    // 다음 레벨까지 필요한 경험치
    public int getExpToNextLevel(int currentExp) {
        int currentLevel = getCurrentLevel(currentExp);
        int totalExpForNext = getTotalExpForLevel(currentLevel + 1);
        
        return totalExpForNext - currentExp;
    }
}

 

🎯 상황 2: 스킬 업그레이드 비용이 등차수열로 증가

 

 

게임 기획:

• 스킬 1레벨 → 2레벨: 50골드
• 스킬 2레벨 → 3레벨: 100골드
• 스킬 3레벨 → 4레벨: 150골드
• 매 레벨마다 50골드씩 증가

 

public class SkillUpgradeSystem {
    private static final int BASE_COST = 50;
    
    // 특정 스킬 레벨까지 업그레이드하는 데 필요한 총 비용
    public int getTotalUpgradeCost(int targetLevel) {
        if (targetLevel <= 1) return 0;
        
        // 등차수열의 합: 50 + 100 + 150 + ... + (targetLevel-1)*50
        int n = targetLevel - 1;
        return BASE_COST * n * (n + 1) / 2;
    }
    
    // 현재 골드로 업그레이드 가능한 최대 레벨
    public int getMaxAffordableLevel(int currentGold, int currentSkillLevel) {
        int currentTotalCost = getTotalUpgradeCost(currentSkillLevel);
        int availableGold = currentGold + currentTotalCost;
        
        // 이진 탐색으로 최대 레벨 찾기
        int left = currentSkillLevel, right = 100;
        int maxLevel = currentSkillLevel;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (getTotalUpgradeCost(mid) <= availableGold) {
                maxLevel = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return maxLevel;
    }
}