문제출처: https://www.acmicpc.net/problem/11899


문제

심심한 승현이는 너무 심심한 나머지 올바른 괄호열을 가지고 놀고 있었습니다.

(()(()))()()

그러다가 어쩌다 보니 괄호열을 부러뜨렸습니다.

(()    ((    )))()    ()

크게 낙담한 승현이는 노력해 보았지만, 대부분이 부러져 버려 단 한 부분만 재사용할 수 있다는 것을 깨닫게 되었습니다.

)))()

승현이는 이 괄호열을 가지고 놀려고 했으나 올바른 괄호열이 아니기 때문에 행복하지 않았습니다. 이를 보던 지학이는 승현이에게 “그러면 앞과 뒤에 적절하게 괄호를 붙이면 올바른 괄호열이 되지 않을까?”라고 했고, 승현이는 조금 생각한 뒤 그렇게 하기로 했습니다. 예를 들어, 위의 올바르지 않은 괄호열의 경우 앞에 여는 괄호 3개를 붙이면 올바른 괄호열이 됩니다.

((()))()

그러나 괄호열을 사서 붙이는 데에는 돈이 들고 많이 붙일수록 놀기가 불편해지기 때문에, 승현이는 가능한 한 괄호열을 적게 추가하려고 합니다.

승현이가 망가뜨리고 사용 가능한 올바르지 않은 괄호열이 주어질 때, 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 구하는 프로그램을 작성하세요.


입력

첫 번째 줄에 올바르지 않은 괄호열 S가 주어집니다. S의 길이는 1 이상 50 이하입니다.


출력

첫 번째 줄에 S를 올바른 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 출력합니다. 불가능한 경우는 주어지지 않습니다.


풀이

자료구조 책에서 다들 구현해봤을 괄호검사와 다를게없는 문제입니다. 어려운건 없지만 코드작성을 위해 알아야 할건 20행이 왼괄호만 해당된다는것28행이 오른괄호일 때 이므로(올바르지못한 수식일 때) 카운팅 해줘야한다는것입니다. 마지막으로 33행에서 스택에 남아있는 수만큼(왼괄호가 남아있을수 있음==필요한 오른괄호의 수) 다시 카운팅하는것으로 마무리합니다.


코드

#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main()
{
	string s;
	cin >> s;
	stack<char>st;
	int cnt = 0;
	for (int i = 0; i < s.size(); i++)
	{
		//비어있지 않을 떄
		if (!st.empty())
		{
			//올바른 짝일 때
			if (s[i] == ')' && st.top() == '(')
				st.pop();
			//아닐 때==왼괄호일떄  
			else
				st.push(s[i]);
		}
		//비어있을 때
		else
		{
			if (s[i] == '(')
				st.push(s[i]);
			else
				cnt++;
		}
	}
	//남아있는 왼괄호 갯수더해줌
	if (!st.empty())
		cnt += st.size();
	cout << cnt << endl;
}


결과

'문제풀이(BOJ) > 스택' 카테고리의 다른 글

[백준 3986] 좋은 단어  (0) 2019.12.08
[백준 9012] 괄호  (0) 2019.12.03
[백준 10828] 스택  (0) 2019.12.03

문제출처: https://www.acmicpc.net/problem/9455


문제

m행 n열로 이루어진 그리드가 주어진다. 일부 칸에는 박스가 들어 있다. 모든 박스가 더 이상 움직일 수 없을 때 까지 아래로 움직인다면, 박스는 쌓여진 상태가 된다.

그림 (a)의 그리드의 크기는 5행 4열이고, 7칸에는 박스가 들어있다. 모든 박스가 계속해서 아래로 움직이면, 그림 (b)와 같이 변하게 된다.

박스가 움직인 거리는 바닥에 쌓이기 전 까지 이동한 칸의 개수이다. 예를 들어, 맨 왼쪽 열에서 가장 위에 있는 박스가 움직인 거리는 2이다. 모든 박스가 이동한 거리 (각 박스가 이동한 거리의 합) 을 구하는 프로그램을 작성하시오. 위의 예제에서 박스 7개가 움직인 거리는 8이다.


입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 m과 n이 주어진다. (1 ≤ m, n ≤ 100) 다음 m개 줄에는 그리드의 각 행의 정보를 나타내는 n개의 정수가 주어진다. 그리드 첫 행부터 마지막 행까지 순서대로 주어진다. 박스가 들어있는 칸은 1로, 다른 칸은 0으로 주어진다. 각 정수 사이에는 공백이 하나 주어진다.


출력

각 테스트 케이스마다 입력으로 주어진 그리드에서 모든 박스가 이동한 거리를 출력한다.


풀이

삼성sw exprt 문제에서 본 것 같은데 단순히 문제를 코드로 구현할 수 있는지를 보는 문제입니다.

각 열 마다 박스가 움직이는 횟수를 알아야하고(box변수), 모든 열을 조사하여 박스의 총 이동횟수를 구해야합니다(ans변수). 방법1(30행~36행)은  박스가 땅에 떨어질때 횟수를 세므로, 마지막인덱스-현재위치-박스움직임의횟수 로 구할 수 있습니다. 방법2는 방법1을 개선한 코드로, 더 직관적이라고 할 수 있습니다.


코드

#include<iostream>
#include<algorithm>
int map[100][100];
using namespace std;
int main()
{
	int t,m,n;
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		//답을 출력하기위한 ans변수
		int ans = 0;
		cin >> m >> n;
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				cin >> map[i][j];
			}
		}
		for (int i = 0; i < n; i++)
		{
			//각 열 마다 박스이동횟수 초기화
			int box = 0;
			for (int j = m - 1; j >= 0; j--)
			{
				//방법1
				//현재자리가 박스 놓여져있을 때
				if (map[j][i] == 1)
				{
					//마지막행인덱스-현재위치-움직인박스길이
					ans += (m - 1) - j - box;
					//박스 한칸움직임.
					box++;
				}

				//방법2
				/*if (map[j][i] == 0)
					box++;
				else
					ans += box;*/
			}
		}
		cout << ans << '\n';
	}
}


결과




'문제풀이(BOJ) > 시뮬레이션(구현)' 카테고리의 다른 글

[백준 2526] 싸이클  (0) 2020.01.09
[백준 11507] 카드셋트  (0) 2020.01.08
[백준 12759] 틱!택!토!  (0) 2020.01.08
[백준 2578] 빙고  (0) 2020.01.06
[백준 1526] 가장 큰 금민수  (0) 2020.01.06

문제출처: https://www.acmicpc.net/problem/12759


문제

틱택토(Tic-Tac-Toe)는 오목과 아주 유사한 형태의 보드게임이다.

게임 방법은 아래와 같다.

  1. 종이 위에 가로줄 2줄 세로줄 2줄을 그린다.
  2. 이렇게 생긴 9칸 위의 빈칸에 플레이어 1은 O, 플레이어 2는 X를 번갈아가며 그린다.
  3. 먼저 O 또는 X를 3개가 직선으로 이어지게 하면 승리하고 게임이 끝난다.
  4. 이어지는 직선이 없고, 더는 그릴 빈칸이 없으면 무승부로 게임이 종료된다.

남녀노소 모두 즐길 수 있는 아주 쉬운 게임이지만, 중간에 끝났는지 눈치를 못 채고 계속하는 경우가 있다. 그래서 당신은 제3의 공정하고 자비 없는 냉정한 심판을 두고 싶었다.

각 플레이어가 교대로 O 또는 X를 그린 위치가 입력되면 누가 언제 이기는지를 출력하는 프로그램을 작성하시오.


입력

첫째 게임을 먼저 시작할 플레이어의 번호가 입력된다. 플레이어의 번호는 1 또는 2이다.

다음 9개의 줄에 게임이 끝날 때까지 번갈아가며 어느 위치에 그렸는지 좌표가 입력된다. 좌표는 가로 행, 세로 열의 순으로 입력된다. 가장 왼쪽 위는 (1, 1), 가장 오른쪽 아래는 (3, 3)이다.

이미 입력된 좌표가 주어지는 경우는 없으며, 항상 게임이 끝나는 입력만 주어진다.


출력

승자가 결정되는 즉시 이긴 플레이어의 번호를 출력한다. 플레이어의 번호는 1 또는 2이다. 무승부라면 0을 출력한다.


풀이

빙고게임처럼 단순한 구현문제이지만 쉽게 구현하지못했고 다른 분의 코드를 참조했습니다.ㅠㅠ 

참조: https://hsdevelopment.tistory.com/213?category=1013710

입력을 받을 때 마다 승부의 여부를 확인합니다. 이 때 25행~28행 처럼 코드를 작성하면 입력을 받고 승부의 여부를 확인했을 때 그 이후의 모든 승부를 확인하지않게됩니다. 문제에서 "승부를 찾는 즉시 출력한다"를 만족합니다.(문제가 모호합니다. "승부를 찾는 즉시 출력한다"가 바로 출력하는게 아니라 승부 확인 후 "그 이후의 모든 연산을 하지않는다"로 해석해야합니다.) 승부는 행,열,대각선(좌->우, 우->좌) 모두 확인합니다.(브루트포스)

게임판의 크기는 [3][3]이지만 시작 좌표는 1,1 이므로 x,y의 index만 조심하면될 것 같습니다.


코드

#include<iostream>
int map[3][3];
using namespace std;
int func(int x);
int main()
{
	int num;
	cin >> num;
	int x, y;
	int value;
	int ans = 0;
	bool check = false;
	//num이1이면O표시, 2이면X표시
	for (int i = 0; i < 9; i++)
	{
		if (i % 2 == 0)value = num;
		else
		{
			if (num == 2)value = 1;
			else value = 2;
		}
		cin >> x >> y;
		x--, y--;
		map[x][y] = value;
		if (!check)
		{
			ans = func(value);
			if (ans != 0)check = true;
		}
	}
	cout << ans << endl;
}
int func(int x)
{
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (map[i][j] != x)break;
			if (j == 2)return x;
		}
	}
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			if (map[j][i] != x)break;
			if (j == 2)return x;
		}
	}
	for (int i = 0; i < 3; i++)
	{
		if (map[i][i] != x)break;
		if (i == 2)return x;
	}
	for (int i = 0; i < 3; i++)
	{
		if (map[i][2 - i] != x)break;
		if (i == 2)return x;
	}
	return 0;
}


결과



'문제풀이(BOJ) > 시뮬레이션(구현)' 카테고리의 다른 글

[백준 11507] 카드셋트  (0) 2020.01.08
[백준 9455] 박스  (0) 2020.01.08
[백준 2578] 빙고  (0) 2020.01.06
[백준 1526] 가장 큰 금민수  (0) 2020.01.06
[백준 2303] 숫자 게임  (0) 2020.01.03

문제출처: https://www.acmicpc.net/problem/11652


문제

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다.

준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.


입력

첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 <= N <= 1000000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다.


출력

첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다.


풀이

정답률이 많이 낮습니다.. 문제분류가 정렬인데 사실 정렬은 sort함수만 써도되니 그건아닌것 같고.. 아마도 가장 많이 갖고있는 수를 구하는 과정에서 어려움을 겪으셨을겁니다. 

일단 입력범위를 보니, 그리고 많이갖고있을 떄 작은 수를 출력하라는 조건에 의해  long long 형의 100만크기의 배열을 선언합시다. 그리고 sort함수로 정렬해요.(퀵정렬은 최악의 경우 O(n^2)이므로 시간초과가 날 수 있지만 sort함수의 평균적 시간복잡도는 O(nlogn)입니다. 찝찝하시면 병합정렬쓰세요! 그리고 이제 답을구하기 위해 변수를 선언합시다. cnt는 연속된 수의 개수를(주의: 0으로 초기화 할시 1 1 1 2 일때 2개가됩니다.) , max는 가장 큰 연속된 개수의 수, index는 가장 큰 연속된 개수를 가질 때 그 위치의값을 나타냅니다. 그리고, 수가 연속될 때, 연속되지 않을 떄의 2가지경우로 나누어서 숫자를 세봅시다. 일단 연속되지않으면 무조건 cnt를 1로 초기화합니다.(0으로 초기화하면 안됩니다. 위에서 얘기했듯이 1 1 1 2 일때 2개가 되죠.)연속될 시, cnt를 한칸 증가시켜주고 max값을 갱신해줍니다. 갱신해 줄 때 그 때의 index를 저장합니다.최종적으로 반복문을 마치고 card[index]가 정답이됩니다. 최종적으로 시간복잡도는 O(nlogn)+O(n)입니다. 그리고 마지막으로,, 아래 채점결과에서 볼 수 있듯이 c++의 입출력함수가 시간을 많이 잡아먹으므로 cin.tie(0); cin.sync_with_stdio(false); 선언을 생활화 합시다.


주의 할것 : 

cnt= 1로 초기화하고 조건식에서 연속되지않을 시 0이 아닌 1로 초기화하기

c++ 입출력 사용 시 개행을 '\n', 입출력 시 cin.tie(0); cin.sync_with_stdio(false); 선언 생활화하기


코드

채점결과 순서대로 각각 

개행:'\n', cin.tie(0),cin.sync_with_stdio(false)선언했을 때 : 28ms

개행:'\n'만 썼을 때 : 120ms

c++입출력사용했을 때 : 136ms

#include<iostream>
#include<algorithm>
using namespace std;
long long card[1000000];
int main()
{
	int n;
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> card[i];
	sort(card, card + n);
	//세기위한 변수, 갯수를 비교하기위한변수
	int cnt = 1, max = 0, index = 0;
	for (int i = 0; i < n - 1; i++)
	{
		if (card[i] == card[i + 1])
		{
			cnt++;
			if (cnt > max)
			{
				max = cnt;
				index = i;
			}
		}
		else
			//0이아닌 1로초기화!
			cnt = 1;
	}
	cout << card[index] << '\n';
	
}

 

결과


문제출처: https://www.acmicpc.net/problem/2578


문제

빙고 게임은 다음과 같은 방식으로 이루어진다.

먼저 아래와 같이 25개의 칸으로 이루어진 빙고판에 1부터 25까지 자연수를 한 칸에 하나씩 쓴다

다음은 사회자가 부르는 수를 차례로 지워나간다. 예를 들어 5, 10, 7이 불렸다면 이 세 수를 지운 뒤 빙고판의 모습은 다음과 같다.

차례로 수를 지워가다가 같은 가로줄, 세로줄 또는 대각선 위에 있는 5개의 모든 수가 지워지는 경우 그 줄에 선을 긋는다.

이러한 선이 세 개 이상 그어지는 순간 "빙고"라고 외치는데, 가장 먼저 외치는 사람이 게임의 승자가 된다.

철수는 친구들과 빙고 게임을 하고 있다. 철수가 빙고판에 쓴 수들과 사회자가 부르는 수의 순서가 주어질 때, 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지를 출력하는 프로그램을 작성하시오.


입력

첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 빙고판에 쓰여진 수와 사회자가 부르는 수는 각각 1부터 25까지의 수가 한 번씩 사용된다.


출력

첫째 줄에 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지 출력한다.


풀이

100퍼센트 구현문제입니다. 사회자가 숫자를 부를 때 마다 빙고인지 아닌지 행,열,대각선 모두 검사해야합니다. 빙고를 확인하는 검사는 행 빙고 검사, 열 빙고 검사, 대각선(좌->우), (우->좌) 총 4가지입니다. 이것을 소스로 구현하면 끝입니다. 중요한 건 42행, 52행 처럼 바깥for문내에 sum을 0으로 초기화 시켜야 그 행 or 열 라인의 빙고를 판별 할 수 있습니다. 대각선 검사는 총 두번밖에안되므로, 그리고 규칙성을 가지므로(0,0,1,1,2,2,   0,4, 1,3, 2,2 등..) 1차원배열로 검사합니다. 그리고 실수하기 쉬운것은 빙고의 개수를 확인하는 cnt변수를 전역변수가 아닌 빙고검사함수내의 지역변수로 선언해야한다는것입니다. 한번 검사하여 빙고가아니면 총 빙고의 갯수를 세는 변수는 초기화가되어야합니다.


코드

#include<iostream>
using namespace std;
int map[5][5];
void func(int call);
bool bingo();
int main()
{
	int call;
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			cin >> map[i][j];
	for (int i = 0; i < 25; i++)
	{
		cin >> call;
		//부르는 값을 0으로바꿈
		func(call);
		//빙고확인//참이면 빙고완료
		if (bingo())
		{
			cout << i + 1 << endl;
			break;
		}
	}
}
void func(int call)
{
	//부르는 값을 0으로초기화
	for (int i = 0; i < 5; i++)
		for(int j=0;j<5;j++)
		if (call == map[i][j])
		{
			map[i][j] = 0;
			return;
		}

}
bool bingo()
{
	int cnt = 0;
	//행 빙고, 열빙고, 대각선 빙고 확인
	for (int i = 0; i < 5; i++){
		int sum = 0;
		for (int j = 0; j < 5; j++) {
			sum += map[i][j];
		}
		if (sum == 0)
			cnt++;
		}

	//열빙고
	for (int i = 0; i < 5; i++) {
		int sum = 0;
		for (int j = 0; j < 5; j++) {
			sum += map[j][i];
		}
		if (sum == 0)
			cnt++;
	}
	
	//대각선빙고: 좌에서 우
	int sum = 0;
	for (int i = 0; i < 5; i++)
		sum += map[i][i];
	if (sum == 0)cnt++;

	//대각선빙고: 우에서 좌
	sum = 0;
	for (int i = 0; i < 5; i++)
		sum += map[i][5 - 1 - i];
	if (sum == 0)cnt++;

	if (cnt >= 3)
		return true;
	else return false;

}


결과

'문제풀이(BOJ) > 시뮬레이션(구현)' 카테고리의 다른 글

[백준 9455] 박스  (0) 2020.01.08
[백준 12759] 틱!택!토!  (0) 2020.01.08
[백준 1526] 가장 큰 금민수  (0) 2020.01.06
[백준 2303] 숫자 게임  (0) 2020.01.03
[백준 10163] 색종이  (0) 2020.01.03

문제출처: https://www.acmicpc.net/problem/2535


문제

최근 아시아 지역의 학생들만 참여하는 정보 올림피아드 대회가 만들어졌다. 이 대회는 온라인으로 치러지기 때문에 각 나라에서 이 대회에 참여하는 학생 수의 제한은 없다. 

참여한 학생들의 성적순서대로 세 명에게만 금, 은, 동메달을 수여한다. 단, 동점자는 없다고 가정한다. 그리고 나라별 메달 수는 최대 두 개다.

예를 들어, 대회 결과가 다음의 표와 같이 주어졌다고 하자.

이 경우, 금메달 수상자는 1번 국가의 1번 학생이고, 은메달 수상자는 1번 국가의 2번 학생이며, 동메달 수상자는 3번 국가의 4번 학생이다. (1번 국가의 3번 학생의 성적이 동메달 수여자보다 높지만, 나라 별 메달 수가 두 개 이하 이므로 1번 국가 3번 학생은 동메달을 받을 수 없다.)

대회 결과가 입력으로 주어질 때, 메달 수상자를 결정하여 출력하는 프로그램을 작성하시오.


입력

첫 번째 줄에는 대회참가 학생 수를 나타내는 N이 주어진다. 단, 3<=N<=100이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학생의 소속 국가 번호, 학생 번호, 그리고 성적이 하나의 빈칸을 사이에 두고 주어진다. 단, 국가 번호는 1부터 순서대로 하나의 정수로 주어지며, 각 학생번호는 각 나라별로 1부터 순서대로 하나의 정수로 주어진다, 점수는 0 이상 1000 이하의 정수이고, 동점자는 없다고 가정한다. 입력으로 제공되는 국가는 적어도 두 나라 이상이다.


출력

메달을 받는 학생들을 금, 은, 동메달 순서대로 한 줄에 한 명씩 출력한다. 즉, 첫 번째 줄에는 금메달 수상자를, 두 번째 줄에는 은메달 수상자를, 세 번째 줄에는 동메달 수상자를 출력한다. 하나의 줄에는 소속국가 번호와 학생 번호를 하나의 빈칸을 사이에 두고 출력한다. 


풀이

구조체+정렬 문제로써, c언어 구조체스타일로 구현할 수 있지만 이럴 때 클래스를 안쓰면 나중에 까먹을까봐 클래스로 구현했습니다.

25행까지는 무리없이 이해가 가실거고, 같은나라에서 두개의 메달이나왔을 때 세번째 메달의 순위를 구하는 방법을 알아봅시다.

방법은 간단합니다. 학생 수가 3~100까지므로 학생이속한 나라의 메달 갯수를 저장하기위해 100크기의 1차원배열을 선언합니다.

그리고 42행을 보면, 보기의 예시처럼 1번국가에서 3개의 메달이 나오는것을 방지하기위해 한 국가에서 메달이 2개까지나왔는지를 검사합니다.

참이면 1증가시켜주고 동메달의 점수를 갖는 사람의 국가가 그 국가일 때 건너뛸 수있도록합니다. 그리고 그 연산을 마치고 cnt를 증가시켜주며 3명까지 출력 시킬 수 있도록합니다!


코드

#include<iostream>
#include<algorithm>
using namespace std;
class info
{
public:
	int born;
	int num;
	int score;
	info() {}
	void setInfo(int born, int num, int score)
	{
		this->born = born;
		this->num = num;
		this->score = score;
	}
	void showInofo()
	{
		cout << this->born << " " << this->num << endl;
	}
	bool operator<(const info&stu) const
	{
		return this->score >stu.score;
	}
};
int check[100];
using namespace std;
int main()
{
	info stu[100];
	int born, num, score;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> born >> num >> score;
		stu[i].setInfo(born, num, score);
	}
	sort(stu, stu + n);
	for (int i = 0,cnt=0; i < n&&cnt<3; i++)
	{
		if (check[stu[i].born] < 2) {
			check[stu[i].born]++;
			stu[i].showInofo();
			cnt++;
		}
	}
}


결과



'문제풀이(BOJ) > 문자열' 카테고리의 다른 글

[백준 11008] 복붙의 달인  (0) 2020.01.10
[백준 12780] 원피스  (0) 2020.01.10
[백준 1075] 나누기(string연습!!)  (0) 2020.01.06
[백준 3181] 줄임말 만들기  (0) 2020.01.02
[백준 9226] 도깨비말  (0) 2019.12.06

문제출처: https://www.acmicpc.net/problem/1526


문제

은민이는 4와 7을 좋아하고, 나머지 숫자는 싫어한다. 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다.

N이 주어졌을 때, N보다 작거나 같은 금민수 중 가장 큰 것을 출력하는 프로그램을 작성하시오.


입력

첫째 줄에 N이 주어진다. N은 4보다 크거나 같고 1,000,000보다 작거나 같은 자연수이다.


출력

첫째 줄에 N보다 작거나 같은 금민수 중 가장 큰 것을 출력한다.


풀이

정답률이 50퍼대라서 괜히 어려운문제같아서 고민했지만 결국 기본에 충실하면 5분컷인 문제입니다. (해보지도 않고 겁부터먹는..)

수가 4또는7의 구성으로 이루어진 수 중 범위내에서 가장 큰 값을 구하는 문제이므로 최대범위값부터 하나씩 줄여가며 

수%10 ==7 or 수%10==4 인 금민수를 구하면됩니다...


코드

#include<iostream>
using namespace std;
bool func(int n);
int main()
{
	int n;
	cin >> n;
	int ans;
	for (int i = n; i >= 4; i--)
	{
		//만약 각 자릿수가 4또는 7이면
		//그때의 i값 저장하고 출력
		if (func(i))
		{
			ans = i;
			break;
		}
	}
	cout << ans << endl;
}
bool func(int n)
{
	while (n)
	{
		//각 자릿수가 4또는7의구성이면 계속진행
		if (n % 10 == 4 || n % 10 == 7)
			n /= 10;
		//false값리턴
		else
			return false;
	}
	return true;
}


결과

'문제풀이(BOJ) > 시뮬레이션(구현)' 카테고리의 다른 글

[백준 12759] 틱!택!토!  (0) 2020.01.08
[백준 2578] 빙고  (0) 2020.01.06
[백준 2303] 숫자 게임  (0) 2020.01.03
[백준 10163] 색종이  (0) 2020.01.03
[백준 12760] 최후의 승자는 누구?  (0) 2020.01.03

문제출처: https://www.acmicpc.net/problem/1075


제목에도 나와있듯이  c++ string기능들을 익히기위해 string 으로 풀어봤습니다.

물론, 문제의 조건을 이용해서 숫자로 푸는게 제일 깔끔하고 코드가 짧습니다. (충분히 푸실 수 있으니 풀이는 생략)

저는 stirng 사용법을 익히고자 아래와 같은 방법으로 풀어보았습니다.


string 사용이 아직 미숙하시면 아래의 링크를 참고해주세요!!

stirng사용법 부수기 : https://jow1025.tistory.com/51


문제

두 정수 N과 F가 주어진다. 지민이는 정수 N의 가장 뒤 두 자리를 적절히 바꿔서 N을 F로 나누어 떨어지게 만들려고 한다. 만약 가능한 것이 여러 가지이면, 뒤 두 자리를 가능하면 작게 만들려고 한다.

예를 들어, N=275이고, F=5이면, 답은 00이다. 200이 5로 나누어 떨어지기 때문이다. N=1021이고, F=11이면, 정답은 01인데, 1001이 11로 나누어 떨어지기 때문이다.


입력

첫째 줄에 N, 둘째 줄에 F가 주어진다. N은 100보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. F는 100보다 작거나 같은 자연수이다.


출력

첫째 줄에 마지막 두 자리를 모두 출력한다. 한자리이면 앞에 0을 추가해서 두 자리로 만들어야 한다.


풀이

코드로 확인하는게 이해가 더 편할 것 같습니다.

말그대로 string사용법을 익히기위한 풀이방식입니다. (이렇게 풀지마세요..굳이...)


코드

#include<iostream>
#include<string>
using namespace std;
int main()
{
	int n, f;
	cin >> n >> f;
	string s = to_string(n);
	//맨 뒤, 맨 뒤-1자릿값 x,y에 저장
	int x = s[s.size() - 1]-'0';
	int y = s[s.size() - 2]-'0';
	//뒤 두자리 뺀 값을 저장
	string temp1 = s.substr(0, s.size() - 2);
	//0부터 하나씩 다 찾아보다가 찾으면 출력
	for (int i = 0; i <= 9; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			//temp1에 0~9값을 추가해가며 f로나눠지는지확인
			int temp2=stoi(temp1 + to_string(i)+to_string(j));
			if (temp2 % f == 0)
			{
				cout << i << j;
				return 0;
			}
		}
	}
}


결과

+ Recent posts