문제링크
문제
세준이는 따분해진 나머지 갑자기 체스 판의 크기를 마음대로 조정하는 체스 판을 만들었다.
세준이는 N*N 크기의 체스 판에 과연 몇 개의 비숍 (BISHOP)을 세울 수 있는지 궁금해 졌다.
비숍 (BISHOP)은 자신의 위치에서 대각선 왼쪽 위, 대각선 왼쪽 아래, 대각선 오른쪽 위, 대각선 오른쪽 아래 () 이렇게 4방향으로 움직일 수 있는 말이다.
체스판의 크기가 주어졌을 때, 서로 잡아먹지 않게 최대로 비숍을 몇 개를 놓을 수 있는지 구하는 프로그램을 작성하시오.
입력
체스판의 크기 N이 주어진다. N은 10진수로 70자리 이하인 자연수이다.
출력
최대로 비숍을 몇 개 놓을 수 있는지 출력한다.
풀이
문제 풀이는 굉장히 쉽다. 직접 그림을 그려보면 n이 1일 때를 제외하고는 n + n - 2가 정답인 것을 금방 알 수 있다.
파이썬이나 자바로는 위의 내용을 그대로 적어 제출하면 되지만 c++에서는 그렇지 않다. N은 10진수로 70자리 이하인 자연수이다. 라는 조건 때문이다.
long long의 자료형을 사용해도 70자리는 택도 없기 때문에 string으로 구현해야 한다. 때문에 코드가 복잡하다..
실제로 c++로 제출한 사람들을 보면 많이 틀렸고, 맞은 사람도 많지 않았다. 아마 위의 조건을 인식하지 못하지 않았을까 생각한다.
코드
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
#include <iostream>
#include <stack>
using namespace std;
string n;
stack<int> s;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
if (n == "1" || n == "2") {
cout << n;
}
else {
int size = n.size();
// 숫자로 변환
for (int i = 0; i < size; i++) {
n[i] = n[i] - '0';
}
// 올림 flag
bool up = false;
for (int i = size - 1; i >= 0; i--) {
if (n[i] * 2 >= 10) {
n[i] = n[i] * 2 - 10;
if (up == true) {
n[i]++;
up = false;
}
up = true;
s.push(n[i]);
}
else {
n[i] = n[i] * 2;
if (up == true) {
n[i]++;
up = false;
}
s.push(n[i]);
}
}
// 올림수 추가 (ex 5 -> 10)
if (up == true) {
s.push(1);
}
size = s.size();
for (int i = 0; i < size - 2; i++) {
cout << s.top();
s.pop();
}
// n-2계산
if (size >= 2) {
int fir = s.top();
s.pop();
int sec = s.top();
int last = fir * 10 + sec;
// last-2<10 : 55.. 처리 위함
// size>2 : 5 처리 위함
if (last - 2 < 10 && size > 2) {
cout << 0 << last - 2;
}
else {
cout << last - 2;
}
}
else {
cout << s.top() - 2;
}
}
}
|
cs |
메모
c++의 한계..라고 해야 하나 다른 언어의 장점이라고 해야하나.. 다른 언어도 어렵지 않을 정도로 구현이 가능하면 풀이 능력이 훨씬 좋아질 것 같다는 생각을 했다.