본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 1673번 : 치킨쿠폰 www.acmicpc.net/problem/1673 1673번: 치킨 쿠폰 강민이는 치킨 한 마리를 주문할 수 있는 치킨 쿠폰을 n장 가지고 있다. 이 치킨집에서는 치킨을 한 마리 주문할 때마다 도장을 하나씩 찍어 주는데, 도장을 k개 모으면 치킨 쿠폰 한 장으로 교환 www.acmicpc.net ad-hoc 문제였습니다. 그 뜻처럼 이런 문제에만 적용되는 유일한 해결책을 찾는 문제입니다. 풀이방법 1. 입력 이 문제는 입력의 끝이 규정되어 있지 않습니다. 따라서 loop탈출을 위해서 파일의 끝을 찾았을 때 입력받고 있었던 loop를 탈출해야 합니다. 파일의 끝은 scanf를 사용해서 입력받았을 때 EOF(End Of File)을 만나면 false(0)을 반환합니다. 2. 쿠폰이 남아 있는 동안 loop..
(C++) - 백준(BOJ) 9933번 : 민균이의 비밀번호 www.acmicpc.net/problem/9933 9933번: 민균이의 비밀번호 첫째 줄에 단어의 수 N (2 ≤ N ≤ 100)이 주어진다. 다음 N개 줄에는 파일에 적혀있는 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자로만 이루어져 있으며, 길이는 2보다 크고 14보다 작은 www.acmicpc.net 문자열 처리 문제였습니다. 풀이방법 1. 입력 : string 1차원 배열 word를 선언한 뒤 n개의 단어를 입력받습니다. 2. 비교 : word의 단어들 중 두 쌍을 뽑아 한쪽을 뒤집어 만약 같다면 비밀번호이므로 출력한 뒤 프로그램을 종료합니다. 이 문제는 조합이 아닙니다. 즉 a,b를 비교했다고 넘어가면 안되며 b,a도 비교해 줘야 맞습니다. 한쪽만 뒤집기 때문에 다른쪽도 나중에 뒤집어..
(C++) - 백준(BOJ) 6236번 : 용돈 관리 www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 이분탐색 문제였습니다. 문제 지문에 오해의 소지가 있어 푸는데 애먹었습니다.. 풀이방법 * k원을 인출했다면 해당 돈이 부족해질 때까지 다음날에도 그 다음 날에도 계속해서 쓸 수 있습니다. 돈이 부족해졌다면 기존에 있는 돈은 넣고 다시 k원을 인출하므로 k원이 됩니다. 1. 인출할 돈을 최소로 하기위해 0원부터 0x3f3f3f3f까지 이분탐색을 위해 범위를 정합니다. 2. 매번 mid마다 체크함수를 실행해줍니다. 모..
(C++) - 백준(BOJ) 20055번 : 컨베이어 벨트 위의 로봇 www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 시뮬레이션 문제였습니다. 문제지문이 조금 이상해서 시간 단축을 위해 몇 가지 정보를 추가해보았습니다. 1. 로봇이 i에서 i + 1번째 칸으로 옮길때 i+1번째 칸만 내구도가 1감소합니다. 2. 로봇이 땅에 내려올 때 N번째 칸의 내구도는 감소하지않습니다. Code #include using namespace std; int n,k; //위층은 0 ~ n-1까지의 벨트 //아래층은 n ~ ..
(C++) - 백준(BOJ) 2206번 : 벽 부수고 이동하기 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net bfs문제였습니다. 풀이방법 1. 정의하기 : 필요한 정보는 (i,j)의 맵에 도착했을 때 벽의 상태 w(0이면 부수지 않음, 1이면 부서짐) 입니다. 따라서 2차원을 두 가지로 나눠서 생각해야하므로 3차원의 visited배열을 이용해 거리와, 벽의 상태, 방문여부를 확인할 수 있도록 저장합니다. 2. bfs함수 시행 : 두 가지 방식으로 시행됩니다. 2-1. 이동할 수 있는 곳이라면 ..
(C++) - 백준(BOJ) 3943번 : 헤일스톤 수열 www.acmicpc.net/problem/3943 3943번: 헤일스톤 수열 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 다음 줄부터 T개의 줄에는 헤일스톤 수열의 시작값 n이 주어진다. (1 ≤ n ≤ 100,000) www.acmicpc.net 구현문제였습니다. * 입출력이 많으므로 시간초과가 나지 않도록 c와 동기화를 끊어줘야 합니다. Code #include #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n, t; int main(){ fastio; cin >> t; while(t--){ cin >> n; int big = n; while(..
(C++) - 백준(BOJ) 1713번 : 후보 추천하기 www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 www.acmicpc.net 시뮬레이션 문제였습니다. * 배열 크기를 조심해야합니다. * 0은 출력되면 안됩니다. Code #include using namespace std; int recommandStat[101]; //추천 수 int pictureStat[21]; //사진 게시 현황 int old[101]; //가장 오래된 사진 int pictureCnt, n,m; void updateTime(){ for(int i = 1; i ..
(C++) - 백준(BOJ) 1592번 : 영식이와 친구들 www.acmicpc.net/problem/1592 1592번: 영식이와 친구들 일단 1번이 공을 잡는다. 1번은 공을 한 번 잡았기 때문에, 공을 3번에게 던진다. 3번은 공을 한 번 잡았기 때문에, 공을 5번에게 던진다. 5번은 2번에게 던지고, 2번은 4번에게 던진다. 4번은 1번에 www.acmicpc.net 구현문제였습니다. Code #include using namespace std; int n,m,l; int throwCnt, cur; int ballCnt[1001]; int main(){ cin >> n >> m >> l; ballCnt[cur] = 1; while(ballCnt[cur] != m){ if(ballCnt[cur] % 2) cur = (cur+l) % n; else cur =..

티스토리툴바