www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 백트래킹 문제이지만 백트래킹으로 안 풀고 브루트포스로 풀었다. (너무 잠이 와서 생각을 멈췄다.) n개의 수가 입력 받으면 그 수의 부분 수열의 합이 주어진 s와 같은게 몇 개나 있는지 구하는 문제이다. 문제 자체는 어렵지 않지만, 백트래킹이 더 코드도 깔끔하고 시간도 줄어서 내일 풀어보려 한다. 브루트포스는 다음과 같이 하면 된다. n=10이라 예를 들면 10으로 만들 수 ..
www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 추가 주어졌을 때 그 추들의 합으로 표현 불가능한 가장 작은 수를 찾는 문제입니다. 우선 추를 정렬 시킨 뒤, 첫 번 째 추가 1보다 크면 무조건 1은 표현할 수 없는 가장 작은 수입니다. 그리고 무게가 1인 추가 있는 경우, 정렬되어 있으므로, 두 번 째 추부터 더하면서 (합 +1)보다 크면 합+1 이란 수는 표현할 수가 없습니다. #include #include #include using namespace std; i..
www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 뭔가 그림만 보면 bfs 같은 걸 이용할 거 같이 생겨서 풀어봤는데 문제를 읽어보니 그냥 노가다 구현이었다. 문제 조건은 다음과 같다. 미세먼지의 양과 공기청정기의 위치가 주어졌을 때 1초동안 다음의 일이 일어난다. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다. (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다. 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로..
www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 www.acmicpc.net 밤도 늦고 해서 그냥 쉬운 문제를 하나 풀어보았다. 얼른 자야겠다. 문제는 간단하다. 정답률이 왜 낮은지 잘 모르겠다. 아마 string으로 받아야되는데 띄어써서 input 해서 그런거 같다. 주어진 직사각형 숫자 판에서 가장 큰 정사각형의 크기를 구하는 것이다. 여기서 정사각형은 각 꼭지점의 수가 모두 일치하면 된다. 최대 크기는 50 x 50 이다. 전체 모든 경우를 다 돌아도 최대 2500 가지이고, ..
www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 간단한 bfs 문제이지만, 초기화를 이상하게 해서 푸는데 20분, 에러 찾는데 1시간이 걸린 문제입니다. 너무 화가 납니다 ㅎㅎㅎ 4자리 소수를 한 자리씩 바꿀 수 있고, 이 바꾼 수 또한 소수여야합니다. 그렇게 한 자리씩 바꾼 수가 목표한 수가 될 때까지 수를 바꾼 횟수의 최솟값을 구하면 됩니다. 에라토스테네스 체를 이용해 1000~9999까지 소수들을 미리 구해준 뒤, bfs를 이용해 각 자리별로 0~9까지로 바꾼 ..