백준 23842번 - 성냥개비

💡 브루트포스 문제를 조금 더 효율적으로 푸는 방법을 고려하자!!

<첫 번째 시도> - 실패..

# 1. 필수적으로 + 와 =을 위해서 4개는 소요된다

# 각 숫자를 구성하는 총 성냥개비 갯수
# 들어갈 수 있는 최소 갯수: 4(11) 최대 갯수: 14(88)
num = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
number = []

N = int(input())

# + 와 = 을 제외한 총 성냥개비 갯수
amount = N - 4

# 숫자에 따른 전체 성냥개비 갯수 저장
for i in range(100):
    if i < 10:
        number.append(6 + num[i])
    else:
        numList = list(str(i))
        number.append(num[int(numList[0])] + num[int(numList[1])])    

flag = 0

# 전체 경우의 수를 살펴보며 해당 경우의 수를 체크
for j in range(100):
    if flag == 1: 
        break
    for k in range(100):
        if flag == 1:
            break
        if number[j] + number[k] < amount - 8:
            continue
        for l in range(100):
            if number[j] + number[k] + number[l] == amount and j + k == l:
                flag = 1
                a = j
                b = k
                c = l
                break
                

if flag == 1:
    if a < 10:
        a = '0' + str(a)
    else:
        a = str(a)
    
    if b < 10:
        b = '0' + str(b)
    else:
        b = str(b)
        
    if c < 10:
        c = '0' + str(c)
    else:
        c = str(c)
    print(a + "+" + b + "=" + c)
else:
    print("impossible")

• 처음부터 각 숫자마다 필요한 성냥개비 수를 먼저 구해서 저장해두고, 조건에 맞는 것을 찾아 보았다.
• flag를 지정해서 만약 조건에 만족되는 상황이 나오면 flag를 1로 바꾸고 break해서 성공, 실패 여부를 구분하려고 하였다.
• 예시에 해당하는 것은 전부 제대로 동작했지만, 자꾸 틀렸다고 나와서 아직은 이유를 모르겠다.. 계속 보면서 찾아보면 업데이트 하겠다!!

<두 번째 시도>

import sys

# 각 숫자를 구성하는 총 성냥개비 갯수
# 들어갈 수 있는 최소 갯수: 4(11) 최대 갯수: 14(88)
num = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# + 와 = 을 제외한 총 성냥개비 갯수
N = int(input()) - 4

# 한자리씩 넣어보기
for i in range(10):
    for j in range(10):
        for k in range(10):
            for l in range(10):
                for m in range(10):
                    for n in range(10):
                        if (num[i] + num[j] + num[k] + num[l] + num[m] + num[n] == N) and (10*i + j + 10*k + l == 10*m + n):
                            print(str(i)+str(j)+'+'+str(k)+str(l)+"="+str(m)+str(n))
                            sys.exit()
                            
print("impossible")

• 오류를 찾기 위해서 고민하던 중, 갑자기 생각이 난 풀이이다!
• 코드의 길이도 짧고, 시간복잡도도 기존 코드와 동일하다.
• 쉽게 생각해서, 2자리의 숫자를 하나의 숫자로 보는 것이 아닌, 각 자리 수를 모두 별개로 보면서 조건에 맞는 경우를 찾아내는 방식이다.
• 각 자리수 별로 for문을 돌려서 조건에 맞는 것을 찾아내고, 찾으면 출력후 exit()로 종료해주었다.

💡 파이썬 코드 중간에서 중지하는 법
=> sys.exit()를 사용한다.

import sys

try:
	# 예외 발생시 종료
	exit(1)
except:
	# 바로 종료
	exit()

• 위처럼 exit는 반환코드를 인자로 받아서 종료 상태를 정할 수 있다.

참조 블로그
https://summertrees.tistory.com/376

오프라인 코테 스터디 (12/30)
참가 인원: 기우석님

• 풀이 방식

for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			string a = to_string(i);
			string b = to_string(j);
			if (a != "0")
				b = a + b;
			fir_num.insert({stoi(b), mp[i] + mp[j]});
			sec_num.insert({stoi(b), mp[i] + mp[j]});
			thi_num.insert({stoi(b), mp[i] + mp[j]});
		}
	}
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			for (int k = 0; k < 100; k++) {
				// 수식이 성립할 때.
				if (i + j == k) {
					if (n - 4 == (fir_num[i] + sec_num[j] + thi_num[k])) {
						if (i < 10) {
							cout << '0' << i << '+';
						}
						else {
							cout << i << '+';
						}
						if (j < 10) {
							cout << '0' << j << '=';
						}
						else {
							cout << j << '=';
						}
						if (k < 10) {
							cout << '0' << k;
						}
						else {
							cout << k;
						}
						return 0;
					}
				}
			}
		}
	}
	cout << "impossible";

• 기존 나의 첫번째 코드와 동일하게 모든 숫자의 성냥개비 수를 구하고,
  for 문을 돌리면서 A+B=C에서 A, B, C의 모든 경우의 수를 고려하셨습니다.
• 이 코드를 참고해서 저의 첫번째 코드를 수정하겠습니다.