[완전 탐색] 백준 문제 풀이 - 1107 리모컨

2022. 7. 12. 23:27· PS 연습
목차
  1. 👩🏻‍💻 문제링크
  2. ✍️ 아이디어 (처음에 잘못 접근함)

👩🏻‍💻 문제링크

https://www.acmicpc.net/problem/1107

 

1107번: 리모컨

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼

www.acmicpc.net

 

✍️ 아이디어 (처음에 잘못 접근함)

1. 문제 이해

  • 처음엔 사용할수 있는 버튼을 가지고 모든 수의 조합을 만들려고 했는데 브루트포스는 그냥 모든 수(0~1000000)을 다 해보면 되는거였다

2. 0~1000000의 수를 다 해보면서..

   1. 이 채널에 고장난 버튼이 없는지

   2. 누를수 있다면 목표 버튼이랑 최소차이가 나는지 확인

3. 고장난 버튼을 체크할때 2가지 방법이 있음

   1. 숫자를 문자열로 바꿔서 인덱스로 각자리수가 고장난 버튼인지 비교

   2. 숫자를 %10으로 1의자리 고장난 버튼인지 확인하고 /=10 으로 한자리씩 땡기기

✍️소스코드

  • 강의를 참고하고 고친 나의 코드
#include <iostream>
#include <algorithm>
using namespace std;
bool broke[10];

bool possible(int x) //x라는 수가 버튼으로 누를수 있는지 없는지 판별
{
	if(x==0) return !broke[0];
	while(x>0)
	{
		if(broke[x%10]==true)
			return false;
		else
			x/=10;
	}
	return true;
}

int lengths(int x) //x라는 수의 자릿수를 판별
{
	if(x==0) return 1;
	int ans = 0;
	while(x>0)
	{
		x/=10;
		ans++;
	}
	return ans;
}

int main()
{
	int n; cin>>n;
	int m; cin>>m;
	int result = abs(n-100);
	for(int i=0; i<m; i++)
	{
		int x; cin>>x;
		broke[x]=true;
	}
	for(int i=0; i<=1000000; i++)
    //1000000까지인 이유?  => 문제에서 이동하려고 하는 채널 N의 범위가 0 ~ 500000 이지만,
    //이동하려는 채널보다 높은 위치에 있을 때 감소하는 범위도 고려해야 하므로..
	{
		if(possible(i)) //i가 리모컨 버튼으로 누를수 있으면..
		{
			int length = lengths(i);
			if(result>abs(i-n)+length)
			{
				result=abs(i-n)+length; //++ -- 갯수랑 자릿수를 더한것
			}
		}
	}
	if(abs(n-100) <= 3)
	{
		result=abs(n-100);
	}
	cout<<result<<'\n';
}

 

  • 다른 사람의 코드 (이 숫자가 버튼 고장난것이 없는지 확인 할때 int를 string으로 고쳐서 확인함)
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;


vector<int> dp;
vector<bool> mal(10,false);

bool check(int now){ //now라는 숫자를 누를때 고장난 버튼이 없는지 체크 

    string s = to_string(now); 숫자를 string으로 바꿈
    for(int i = 0; i <s.length();i++){
        if(mal[s[i]-48]){
            return false;
        }

    }

    return true;

}



int main(){

    int n,c;
    cin>>n>>c;

    int tmp;

    for(int i = 0; i < c; i++){
        cin>>tmp;
        mal[tmp] = true;
    }


    string st = to_string(n);

    int minimum = abs(n-100);
    for(int i = 0; i <= 1000000; i++){
        if(check(i)){
            int tmp = abs(n-i)+to_string(i).length();
            minimum = min(minimum,tmp);
        }

    }


    cout<<minimum<<endl;


    return 0;
}

 

체감난이도 걸린시간 참고 사용 문법
상 1hour 강의 참고 완전 탐색(그냥 해보기)

'PS 연습' 카테고리의 다른 글

[완전 탐색] 백준 문제 풀이 - 15650 N과 M (2)  (0) 2022.07.17
[완전 탐색] 백준 문제 풀이 - 15649 N과 M (1)  (0) 2022.07.16
[완전 탐색] 백준 문제 풀이 - 1476 날짜 계산  (0) 2022.07.10
[완전 탐색] 백준 문제 풀이 - 3085 사탕 게임  (0) 2022.07.10
[DP] 백준 문제 풀이 - 17404 RGB거리 2  (0) 2022.07.09
  1. 👩🏻‍💻 문제링크
  2. ✍️ 아이디어 (처음에 잘못 접근함)
'PS 연습' 카테고리의 다른 글
  • [완전 탐색] 백준 문제 풀이 - 15650 N과 M (2)
  • [완전 탐색] 백준 문제 풀이 - 15649 N과 M (1)
  • [완전 탐색] 백준 문제 풀이 - 1476 날짜 계산
  • [완전 탐색] 백준 문제 풀이 - 3085 사탕 게임
생선묵김치찌개
생선묵김치찌개
생선묵김치찌개
준혁's 코딩 연구기록
생선묵김치찌개
전체
오늘
어제
  • 분류 전체보기 (96)
    • Java (5)
    • Spring Boot (3)
    • 자료구조 (8)
    • 네트워크 (4)
    • 데이터베이스 (4)
    • 기술적 고민 (17)
      • Side Match (13)
      • 자리나따 (4)
    • C++ (3)
    • Algorithm (4)
    • PS 연습 (38)
    • 잡동사니 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 스택
  • 배열 리스트
  • 해커톤
  • DN
  • 열혈 자료구조
  • 완전탐색
  • Stream
  • sentry
  • 백준 골드
  • 자료구조
  • 백준
  • 양방향 연결 리스트
  • 예외처리
  • 트리
  • 원형 연결 리스트
  • 스프링
  • 큐
  • 단순 연결 리스트
  • CPP
  • 브루트 포스
  • dp
  • 재귀
  • open api
  • ㄱ
  • 알고리즘
  • backend
  • 이진트리
  • 파일 업로드
  • 수식트리
  • aws rds

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
생선묵김치찌개
[완전 탐색] 백준 문제 풀이 - 1107 리모컨
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.