728x90

백준에서 가장 많이 풀린 문제 TOP 100중 한 문제

 

5622번: 다이얼

문제 상근이의 할머니는 아래 그림과 같이 오래된 다이얼 전화기를 사용한다. 전화를 걸고 싶은 번호가 있다면, 숫자를 하나를 누른 다음에 금속 핀이 있는 곳 까지 시계방향으로 돌려야 한다. 숫자를 하나 누르면 다이얼이 처음 위치로 돌아가고, 다음 숫자를 누르려면 다이얼을 처음 위치에서 다시 돌려야 한다. 숫자 1을 걸려면 총 2초가 필요하다. 1보다 큰 수를 거는데 걸리는 시간은 이보다 더 걸리며, 한 칸 옆에 있는 숫자를 걸기 위해선 1초씩 더 걸린다.

www.acmicpc.net

 

s = input()
total = 0
for i in s:
    if i == 'A' or i == 'B' or i == 'C':
        total += 3
    elif i == 'D' or i == 'E' or i == 'F':
        total += 4
    elif i == 'G' or i == 'H' or i == 'I':
        total += 5
    elif i == 'J' or i == 'K' or i == 'L':
        total += 6
    elif i == 'M' or i == 'N' or i == 'O':
        total += 7
    elif i == 'P' or i == 'Q' or i == 'R' or i == 'S':
        total += 8
    elif i == 'T' or i == 'U' or i == 'V':
        total += 9
    elif i == 'W' or i == 'X' or i == 'Y' or i == 'Z':
        total += 10
print(total)
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 1475번 방 번호  (0) 2020.01.20
[백준] 2747번 피보나치 수  (0) 2020.01.20
[백준] 1316번 그룹 단어 체커  (0) 2020.01.20
[백준] 2839번 설탕배달  (0) 2020.01.20
[백준] 4344번 평균은 넘겠지  (0) 2020.01.20
728x90

백준에서 가장 많이 풀린 문제 TOP 100중 한 문제

 

1316번: 그룹 단어 체커

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

www.acmicpc.net

n = int(input())
count = 0
for i in range(n):
    li = []
    s = input()
    flag = True
    for j in s:
        if j in li:
            if li[-1] == j:
                continue
            else:
                flag = False
                break
        else:
            li.append(j)
    if flag:
        count += 1
print(count)
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 2747번 피보나치 수  (0) 2020.01.20
[백준] 5622번 다이얼  (0) 2020.01.20
[백준] 2839번 설탕배달  (0) 2020.01.20
[백준] 4344번 평균은 넘겠지  (0) 2020.01.20
[백준] 10172번 개  (0) 2020.01.20
728x90

백준에서 가장 많이 풀린 문제 TOP 100 중 한 문제

 

2839번: 설탕 배달

문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수

www.acmicpc.net

1월 20일에 파이썬으로 풀어보고

n = int(input())
five = n // 5
three = 0
find = False
while five >= 0:
    if five * 5 + three * 3 == n:
        find = True
        break
    while five * 5 + three * 3 <= n:
        if five * 5 + three * 3 == n:
            find = True
            break
        three += 1
    if find:
        break
    five -= 1
if find:
    print(five + three)
else:
    print(-1)

두 달 반 후인 4월 6일에 또 다시 풀어보았다.

이번에는 C++로 풀어봤다.

#include <iostream>
using namespace std;


int main() {
	int n;
	cin >> n;
	int count = 0;
	while (true) {
		if (n < 0)
			break;
		if (n % 5 == 0) 
			break;
		else {
			n -= 3;
			count++;
		}
	}
	if (n < 0) cout << -1;
	else cout << count + n / 5;
	return 0;
}

3kg 짜리 설탕을 최대한 적게 쓰고 5kg 짜리 설탕을 최대한 많이 써야되기 때문에 n이 5로 나눠떨어질 때까지 3을 빼주었다. 빼 줄 때마다 3kg짜리 설탕을 한 봉지 사용하는 것이기 때문에 count 변수에 1씩 더해주었다. 그 과정에서 n이 음수가 되면 바로 while문을 빠져나와 -1을 출력하게 했고 5로 나눠떨어지면 while문을 빠져나와 count와 n/5를 더해주었다. count는 3kg짜리 설탕의 개수이고 n / 5는 5kg짜리 설탕의 개수이다. 그 둘을 더해주면 된다.

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 5622번 다이얼  (0) 2020.01.20
[백준] 1316번 그룹 단어 체커  (0) 2020.01.20
[백준] 4344번 평균은 넘겠지  (0) 2020.01.20
[백준] 10172번 개  (0) 2020.01.20
[백준] 10988번 팰린드롬인지 확인하기  (0) 2020.01.19
728x90

백준에서 가장 많이 풀린 문제 TOP 100 중 한 문제

 

4344번: 평균은 넘겠지

문제 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. 입력 첫째 줄에는 테스트 케이스의 개수 C가 주어진다. 둘째 줄부터 각 테스트 케이스마다 학생의 수 N(1 ≤ N ≤ 1000, N은 정수)이 첫 수로 주어지고, 이어서 N명의 점수가 주어진다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 출력 각 케이스마다 한 줄씩 평균을 넘는 학생들의 비율을 반올림하여 소수점 셋째 자

www.acmicpc.net

기억하자 파이썬에서 반올림은 round(실수, 소수점 아래 몇 째자리까지)

0까지 다 표현하고  싶다면 print("%.3f"%5.2156545435) 이런 식으로

c = int(input())
li = []
for i in range(c):
    from sys import stdin
    li.append(list(map(int, stdin.readline().split()))[1:])
above_avg = []
for i in li:
    avg = sum(i) / len(i)
    count = 0
    for j in i:
        if j > avg:
            count += 1
    above_avg.append(100 * count / len(i))
for i in above_avg:
    print("%.3f"%i, end="")
    print("%")
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 1316번 그룹 단어 체커  (0) 2020.01.20
[백준] 2839번 설탕배달  (0) 2020.01.20
[백준] 10172번 개  (0) 2020.01.20
[백준] 10988번 팰린드롬인지 확인하기  (0) 2020.01.19
[백준] 17072번 아스키 아트  (0) 2020.01.19
728x90

백준에서 가장 많이 풀린 문제 TOP 100중 한 문제이다.

 

10172번: 개

문제 아래 예제와 같이 개를 출력하시오. 입력 출력 예제 입력 1 복사 예제 출력 1 복사 |\_/| |q p| /} ( 0 )"""\ |"^"` | ||_/=\\__|...

www.acmicpc.net

이게 정답률이 왜 30%대인거지?

print("|\_/|")
print("|q p|   /}")
print('( 0 )"""\\')
print('|"^"`    |')
print("||_/=\\\\__|")
728x90
728x90
 

10988번: 팰린드롬인지 확인하기

첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다.

www.acmicpc.net

파이썬은 문자열이나 리스트 다루기가 굉장히 편하다는 것을 다시 한 번 느낀다.

s[-1] 이런 음수 인덱스가 된다는게  참 편리하다.

s = input()
flag = 1
for i in range(len(s) //2):
    if s[i] != s[-(i + 1)]:
        flag = 0
        break
print(flag)
728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 4344번 평균은 넘겠지  (0) 2020.01.20
[백준] 10172번 개  (0) 2020.01.20
[백준] 17072번 아스키 아트  (0) 2020.01.19
[백준] 17070번 파이프 옮기기 1  (0) 2020.01.18
[백준] 2442번 별 찍기 - 5  (0) 2020.01.18
728x90

2019 연세대학교 컴퓨터과학과 프로그래밍 경진대회 A번 문제

 

17072번: 아스키 아트

위와 같이, 아스키 문자로 그린 그림을 ‘아스키 아트’ 라고 한다. 우리가 알고 있는 일반적인 그림 파일(.jpg, .png 등)들은 기본적으로 해상도에 맞게 픽셀 단위로 분할된 2차원 그리드에 대해 각 픽셀의 정보를 담는 방식으로 저장된다. 이 정보에는 여러 가지가 있으나, 그중 ‘R’, ‘G’, ‘B’ 값은 ‘Red’, ‘Green’, ‘Blue’의 3색이 각각 어느 정도 섞여 있는지를 나타내 주는 지표이며, 각 값은 0 이상 255 이하의 범위에 있

www.acmicpc.net

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> li(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int r, g, b;
			cin >> r >> g >> b;
			li[i][j] = 2126 * r + 7152 * g + 722 * b;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (li[i][j] < 510000)
				cout << (char)35;
			else if (li[i][j] < 1020000)
				cout << (char)111;
			else if (li[i][j] < 1530000)
				cout << (char)43;
			else if (li[i][j] < 2040000)
				cout << (char)45;
			else cout << (char)46;
		}
		cout << endl;
	}
	return 0;
}

 

728x90
728x90

삼성 A형 기출 문제인 17070번

 

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이

www.acmicpc.net

이렇게 BFS로 풀어서 제출했는데 시간초과가 났다.

n = int(input())
from sys import stdin
li = []
for i in range(n):
    li.append(list(map(int, stdin.readline().split())))
import collections
q = collections.deque()
q.append(((0, 0), (0, 1)))
count = 0
while q:
    cur = q.popleft()
    if cur[1] == (n - 1, n - 1):
        count += 1
    if cur[0][0] == cur[1][0]:
        if cur[1][1] + 1 < n and li[cur[1][0]][cur[1][1] + 1] == 0:
            q.append((cur[1], (cur[1][0], cur[1][1] + 1)))
        if cur[1][1] + 1 < n and cur[1][0] + 1 < n and li[cur[1][0]][cur[1][1] + 1] == 0 and li[cur[1][0] + 1][cur[1][1]] == 0 and  li[cur[1][0] + 1][cur[1][1] + 1] == 0:
            q.append((cur[1], (cur[1][0] + 1, cur[1][1] + 1)))
    elif cur[0][1] == cur[1][1]:
        if cur[1][0] + 1 < n and li[cur[1][0] + 1][cur[1][1]] == 0:
            q.append((cur[1], (cur[1][0] + 1, cur[1][1])))
        if cur[1][1] + 1 < n and cur[1][0] + 1 < n and li[cur[1][0]][cur[1][1] + 1] == 0 and li[cur[1][0] + 1][cur[1][1]] == 0 and  li[cur[1][0] + 1][cur[1][1] + 1] == 0:
            q.append((cur[1], (cur[1][0] + 1, cur[1][1] + 1)))
    else:
        if cur[1][1] + 1 < n and li[cur[1][0]][cur[1][1] + 1] == 0:
            q.append((cur[1], (cur[1][0], cur[1][1] + 1)))
        if cur[1][0] + 1 < n and li[cur[1][0] + 1][cur[1][1]] == 0:
            q.append((cur[1], (cur[1][0] + 1, cur[1][1])))
        if cur[1][1] + 1 < n and cur[1][0] + 1 < n and li[cur[1][0]][cur[1][1] + 1] == 0 and li[cur[1][0] + 1][cur[1][1]] == 0 and  li[cur[1][0] + 1][cur[1][1] + 1] == 0:
            q.append((cur[1], (cur[1][0] + 1, cur[1][1] + 1)))
print(count)

찾아보니까 이 방법으로 풀려면 파이썬이 아닌 다른 언어로 풀어야 한다고 한다.

파이썬으로 풀어서 맞으신 분들은 다 동적계획법으로 푸신 분들만 맞았다고 한다.

역시 알고리즘 풀 때 쓰는 언어를 C++로 바꿔야 하는 걸까

가장 오래 배운 언어가 C++(2018년 3월에 처음 접함)이고 그 다음이 Java(2018년 9월에 처음 접함), 그리고 파이썬(2019년 9월에 처음 접함)이 가장 최근에 배운건데

요즘에 안 써서 그런지 C++은 어색해지고 오히려 배운지 6개월도 안 된 언어인 파이썬이 가장 편해졌다.

파이썬이 문자열 다루기도 좋고 다른 부분에서도 정말 편한데 고민이다.

 

다음 날 2020.01.19

위의 코드를 그대로 C++로 바꿔서 성공

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<vector> li(n, vector(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> li[i][j];
		}
	}
	queue<pair<pair<int, int>, pair<int, int>>> q;
	q.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
	int count = 0;
	while (!q.empty()) {
		int row1 = q.front().first.first;
		int col1 = q.front().first.second;
		int row2 = q.front().second.first;
		int col2 = q.front().second.second;
		q.pop();
		if (row2 == n - 1 && col2 == n - 1) {
			count++;
			continue;
		}
		if (row1 == row2) {
			if (col2 + 1 < n && li[row2][col2 + 1] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2, col2 + 1)));
			if (col2 + 1 < n && row2 + 1 < n && li[row2][col2 + 1] == 0 && li[row2 + 1][col2] == 0 && li[row2 + 1][col2 + 1] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2 + 1, col2 + 1)));
		}
		else if (col1 == col2) {
			if (row2 + 1 < n && li[row2 + 1][col2] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2 + 1, col2)));
			if (col2 + 1 < n && row2 + 1 < n && li[row2][col2 + 1] == 0 && li[row2 + 1][col2] == 0 && li[row2 + 1][col2 + 1] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2 + 1, col2 + 1)));
		}
		else {
			if (col2 + 1 < n && li[row2][col2 + 1] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2, col2 + 1)));
			if (row2 + 1 < n && li[row2 + 1][col2] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2 + 1, col2)));
			if (col2 + 1 < n && row2 + 1 < n && li[row2][col2 + 1] == 0 && li[row2 + 1][col2] == 0 && li[row2 + 1][col2 + 1] == 0)
				q.push(make_pair(make_pair(row2, col2), make_pair(row2 + 1, col2 + 1)));
		}
	}
	cout << count << endl;
	return 0;
}

역시 C/C++이 속도 면에서는 확실히 우수하다.

<tuple>이라는 라이브러리의 pair과 make_pair() 함수 꼭 기억해야겠다.

이걸 이용하니 클래스나 구조체를 따로 만들지 않아도 돼서 편하다.

728x90
728x90

별찍기 문제집의 5번째 문제

 

2442번: 별 찍기 - 5

첫째 줄에는 별 1개, 둘째 줄에는 별 3개, ..., N번째 줄에는 별 2×N-1개를 찍는 문제 별은 가운데를 기준으로 대칭이어야 한다.

www.acmicpc.net

n = int(input())
for i in range(1, n + 1):
    print(" " * (n - i), end="")
    print("*" * (2 * i - 1))
728x90
728x90

별 찍기 문제집의 3번째 문제이다

 

2440번: 별 찍기 - 3

첫째 줄에는 별 N개, 둘째 줄에는 별 N-1개, ..., N번째 줄에는 별 1개를 찍는 문제

www.acmicpc.net

n = int(input())
for i in range(n, 0, -1):
    print("*" * i)
728x90

+ Recent posts