본문 바로가기

분류 전체보기

 (111)
백준 15651 N과 M (3) 문제 링크: https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 중복순열을 출력하는 문제이다. 똑같은 숫자가 또 나와도 되므로, 이 문제 역시 사용했는지 여부를 나타내는 used배열을 사용하지 않았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include using namespace std; int n, m, a[10]; void solve(..
백준 15650 N과 M (2) 문제 링크: https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 조합 (combination)을 출력하는 문제이다. 예를 들어 n = 4, m = 2인 경우에 1 2, 1 3, 1 4, 2 3, 2 4, 3 4와 같이 총 4C2 = 6가지 경우를 출력해야 한다. 순열에서와 같이 이미 사용했는지 여부를 표시할수 있는 used 배열이 필요가 없다. start라는 변수가 하나 추가되어있는데, start보다 큰 숫자가 더 뒤의 index에서 나..
중복 순열 (재귀, 백트래킹) https://yabmoons.tistory.com/123?category=838490 [ 순열과 조합 구현 ] 재귀를 통한 구현(4 - 중복순열) (C++) 지난 글에서 중복조합에 대해서 알아보았다. 이번 시간에는 중복 순열에 대해서 알아보도록 하자. [ 조합 알아보기(Click) ] [ 순열 알아보기(Click) ] [ 중복조합 알아보기(Click) ] 중복순열을 알아보기전, 먼저.. yabmoons.tistory.com 1 2 3에서 2개를 뽑는경우 순열: 1 2, 1 3, 2 1, 2 3, 3 1, 3 2 중복 순열: 1 1, 1 2, 1 3, 2 1, 2 2, 2 3, 3 1, 3 2, 3 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..
백준 15649 N과 M (1) 문제 링크: https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 순열 (permutation)을 출력하는 문제이다. 예를 들어 n = 3, m = 2인 경우에서 1 2, 1 3, 2 1, 2 3, 3 1, 3 2와 같이 총 3P2 = 6가지 경우를 출력해야 하는 문제이다. 재귀함수 solve 내부를 보면, idx가 m이 될때 출력해줘야 하고, m이 되기 전에는 a 배열에 어떤 숫자들이 어떻게 들어가는지를 결정해야 한다. 숫자를 1부터 n..
백준 1748 수 이어 쓰기 1 문제 링크: https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. www.acmicpc.net 120을 예로 들면, 1부터 120까지 120개의 수가 적어도 한자리씩은 차지한다. 10부터 120까지 120 - 9 = 111개의 수가 적어도 두자리씩은 차지한다. 그리고 100 부터 120까지 120 - 9 - 90 = 21개의 수가 적어도 세자리씩은 차지한다. 따라서 120 + 111 + 21 = 252라는 답을 구할수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; int main() { io..
백준 6064 카잉 달력 문제 링크: https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 www.acmicpc.net i를 y로 시작해서 n씩 증가시키면서 for문을 돌리다가 i를 m으로 나눈 나머지가 x일때의 i값이 답이다. 다시 말해서, 년도의 두번째 숫자..
백준 14500 테트로미노 문제 링크: https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 가능한 회전과 대칭을 고려하면 총 19가지 가능한 테트로미노의 모양이 나오고, 전체 종이를 훑으면서 가능한 칸마다 19..
백준 1107 리모컨 문제 링크: https://www.acmicpc.net/problem/1107 불러오는 중입니다... 0번 채널부터 1000000번 채널까지 어느채널에서 가장 적은 수의 버튼을 눌러서 n번 채널로 갈수 있는지 체크하면 된다. 처음에는 isPossible 함수(주어진 채널을 누를때 고장난 버튼이 있는지 확인하는 함수, 주어진 채널이 0일때는 while(num)문이 아예 돌아가지 않기 때문에 예외 처리를 했다.)와 numDigits 함수(주어진 채널로 갈때 눌러야 하는 버튼수를 리턴하는 함수)를 이용해서 아래와 같이 코드를 짰다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3..

티스토리툴바