📝1712번: 손익분기점
낮은 난이도에도 불구하고 정답률이 26%인 이유를 알 것 같은 문제
처음엔 cnt변수를 int형으로 선언해서 while로 증가시키며 풀다가
마지막 test case에서오버플로우(?)발견, cnt를 long long으로 선언
출력은 잘 되나 시간초과가 날 것 같음을 직감
결국 while 없이 수식으로 풀기로 코드를 수정
💻소스코드
#include <iostream>
using namespace std;
int main(void) {
int fixed, flexible, price;
cin >> fixed >> flexible >> price;
if (flexible >= price)
cout << "-1\n";
else
cout << (fixed / (price - flexible)) + 1;
return 0;
}📝2869번: 달팽이는 올라가고 싶다
3트까지만해도 백준에 예시로 나온 test case를 모두 통과했다
그런데 시간초과도 아니고 자꾸 틀렸다고 떠서
다른 test case를 생각해봤다
1)height <= climb일때 1이 출력되는 것을 빠뜨림
2)(height - climb) % (climb - slip) == 0
mod 연산자로 케이스를 나눴어야 완벽한데 div 연산자로 분기해서 틀린 듯
4트해서 맞음
💻소스코드
#include <iostream>
using namespace std;
int main(void) {
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int height, slip, climb;
cin >> climb >> slip >> height;
if (height <= climb)
cout << "1\n";
else if ((height - climb) % (climb - slip) == 0)
cout << ((height - climb) / (climb - slip)) + 1;
else
cout << ((height - climb) / (climb - slip)) + 2;
return 0;
}📝2292번: 벌집
규칙성은 금방 찾았는데 코드화가 오래걸렸다
예시를 나열하자마자 코드가 떠올랐다
1 + 6 x 0 < N <= 1 + 6 x 1
1 + 6 x 1 < N <= 1 + 6 x 3
1 + 6 x 3 < N <= 1 + 6 x 6
1 + 6 x 6 < N <= 1 + 6 x 10
머릿속에서 이것저것 복잡하게 생각할 것이 아니라
손으로 한번만 써보자
💻소스코드
#include <iostream>
using namespace std;
int main(void) {
int N;
int i = 0, j = 1, n = 2, cnt = 1;
cin >> N;
while (1){
if (N == 1){
cout << "1\n";
break;
}
cnt++;
if (1 + 6 * i < N && N <= 1 + 6 * j){
cout << cnt;
break ;
}
i = j;
j += n++;
}
return 0;
}📝10250번: ACM 호텔
세로로 층 수를 계속 채우고 그 다음 가로로 한 칸 가서 층 수를 채우면 되는 문제
주어진 그림을 보면서 생각하면 훨씬 수월했을 텐데
아이패드 사고 싶다
💻소스코드
#include <iostream>
using namespace std;
int main(void) {
int test; // test case
int height, width, n; // 호텔의 층 수, 방 수, n번째 손님
cin >> test;
for(int i = 0; i < test; i++){
cin >> height >> width >> n;
int room = 0, floor; // 방 배정
floor = n % height;
if (floor == 0)
floor = height;
while (n > 0){
n -= height;
room++;
}
if (room < 10)
cout << floor << "0" << room << "\n";
else
cout << floor << room << "\n";
}
return 0;
}📝1193번: 분수 찾기
돌아서 돌아서 가다가 지름길을 발견한 기분이었던 문제
대각선을 카운트해서 홀수 번째와 짝수 번째를 분기
💻소스코드
#include <iostream>
using namespace std;
int main(void) {
int X;
cin >> X;
int i = 1; // 대각선 행
while (X > i){
X -= i;
i++;
}
if (i % 2 == 1)
cout << i + 1 - X << "/" << X << "\n";
else
cout << X << "/" << i + 1 - X << "\n";
return 0;
}📝2775번: 부녀회장이 될테야
k층 n호에 사는 주민 수를 구하고 출력해야되는 문제
결국 k-1층에서 1호부터 n호까지 사는 모든 주민 수의 합을 구하면 끝
💻소스코드
#include <iostream>
using namespace std;
int neighbor(int k, int n){ // 거주민 수의 합
int sum = 0;
if (k == 0)
return n;
for (int i = 1; i <= n; i++)
sum += neighbor(k - 1, i);
return sum;
}
int main(void) {
int test; // test case
int k, n; // k층, n호: k는 0층부터, n은 1호부터
int sum = 0;
cin >> test;
for(int i = 0; i < test; i++){
cin >> k >> n;
sum = neighbor(k, n);
cout << sum << "\n";
}
return 0;
}📝2839번: 설탕 배달
Greedy alghrithm 문제
5kg 봉지가 최대한 많아야 더 적은 갯수의 봉지를 가져갈 수 있다
그래서 5로 나눈 값을 먼저 구한 뒤, 5kg 봉지를 하나씩 빼면서
3으로 나눈 나머지가 0이라면 그 값을 출력하면 된다
💻소스코드
#include <iostream>
using namespace std;
// greedy algorithm
int main(void) {
int kg;
int a, b; // a는 5kg봉지 수, b는 3kg봉지 수
cin >> kg;
a = kg / 5;
while (a >= 0){
if ((kg - 5 * a) % 3 == 0){
b = (kg - 5 * a) / 3;
cout << a + b;
break;
}
a--;
}
if (kg != 5 * a + 3 * b)
cout << "-1\n";
return 0;
}📝10757번: 큰 수 A+B
8bit unsigned long long으로 담을 수 있는 정수 범위마저 초과했던 문제
python은 큰 수를 자유자재로 다룰 수 있고
java는 BigInteger를 지원하는데
C++로 하려니까 백준 기본수학 단계를 통틀어서 풀이 시간이 가장 오래걸렸다
디버깅을 좀 많이해서 코드는 복잡해졌으나 알고리즘은 간단하다
1. 큰 수를 정수형으로 담을 수 없기 때문에 두 개의 string으로 받는다
2. 덧셈은 일의 자리부터 할거니까 일의 자리부터(string의 맨 뒤부터) int형 배열에 차곡차곡 넣는다 (아스키 코드 변환 필수)
3. 두 문자열 중 더 긴 문자열의 길이를 따로 저장한다(더 큰 자릿수를 기준으로 계산)
4. 일의 자리부터 더하는데 합이 10이 넘어가면 자리올림을 해준다(새로운 배열에 더한 값을 할당)
5. 이 때 자리올림이 연속으로 발생하는 경우를 처리해준다
6. 가장 큰 자릿수부터 출력하면 끝
💻소스코드
#include <iostream>
#include <string>
using namespace std;
int main(void) {
int A[10001] = { 0 }, B[10001] = { 0 }; // 0 < A, B < 10^10000
int res[10002] = { 0 }; // A + B 계산 결과를 할당
string s1, s2; // 수가 너무 커서 문자열로 입력받음
int idx; // res 출력 시 사용할 인덱스
int n; // s1과 s2 중 더 큰 자릿수를 저장
cin >> s1 >> s2;
int n1 = s1.length() - 1;
int n2 = s2.length() - 1;
for(int i = 0; i < s1.length(); i++){ // 덧셈은 일의자리부터 하니까
A[i] = s1[n1] - '0';
n1--;
}
for(int i = 0; i < s2.length(); i++){ // 일의 자리부터 차곡차곡 넣는다
B[i] = s2[n2] - '0';
n2--;
}
if (s1.length() > s2.length())
n = s1.length();
else
n = s2.length();
for(int i = 0; i < n; i++){
int sum = A[i] + B[i];
if (sum >= 10){
res[i + 1]++; // 자리올림
res[i] += sum - 10;
if (res[i] >= 10){ // 자리올림 한번 더
res[i + 1]++;
res[i] = res[i] % 10;
}
}
else{
res[i] += sum;
if (res[i] >= 10){
res[i + 1]++;
res[i] = res[i] % 10;
}
}
}
idx = n;
if (res[idx] > 0){
for(int i = idx; i >= 0; i--)
cout << res[i];
}
else{
for(int i = idx - 1; i >= 0; i--)
cout << res[i];
}
return 0;
}